\chapter{Neural Network Models and Functions}
\label{ImplemModels}
\thispagestyle{empty}

The following chapter introduces the models and learning functions
implemented in SNNS. A strong emphasis is placed on the models that
are less well known. They can not, however, be explained
exhaustively here. We refer interested users to the literature.


\section{Backpropagation Networks}
\index{Backpropagation Networks}

\subsection{Vanilla Backpropagation}

The standard backpropagation learning algorithm introduced
by~\cite{rum861} and described already in section~\ref{learning} is
implemented in SNNS. It is the most common learning algorithm. Its
definition reads as follows:

\begin{eqnarray*}
        \Delta w_{ij} & = & \eta \  \delta_{j} \  o_{i}\\
        \delta_{j}    & = & \left\{
        \begin{array}{ll}
        f'_{j}(net_{j})(t_{j} - o_{j}) &
        \mbox{if unit $j$ is an output unit}\\
        f'_{j}(net_{j}) \sum_{k} \delta_{k} w_{jk} & 
         \mbox{if unit $j$ is a hidden unit}\\
        \end{array}
        \right. \\
\end{eqnarray*}

This algorithm is also called {\sl online backpropagation} because it
updates the weights after every training pattern.


\subsection{Enhanced Backpropagation} 
An enhanced version of backpropagation uses a momentum term and flat
spot elimination. It is listed among the SNNS learning functions
as {\tt BackpropMomentum}.

The momentum term introduces the old weight change as a parameter for
the computation of the new weight change. This avoids oscillation
problems common with the regular backpropagation algorithm when the error
surface has a very narrow minimum area. The new weight change is
computed by
\begin{eqnarray*} 
   \Delta w_{ij}(t+1) = 
        \eta * \delta_{j} * o_{i} + \alpha \Delta w_{ij}(t) 
\end{eqnarray*}
$\alpha$ is a constant specifying the influence of the momentum. 

The effect of these enhancements is that flat spots of the error
surface are traversed relatively rapidly with a few big steps, while the step
size is decreased as the surface gets rougher. This adaption of the
step size increases learning speed significantly.

{\bf Note} that the old weight change is lost every time the parameters
are modified, new patterns are loaded, or the network is modified.


\subsection{Batch Backpropagation} 
Batch backpropagation has a similar formula as vanilla
backpropagation. The difference lies in the time when the update of
the links takes place. While in vanilla backpropagation an update step
is performed after each single pattern, in batch backpropagation all
weight changes are summed over a full presentation of all training
patterns (one epoch). Only then, an update with the accumulated weight
changes is performed. This update behavior is especially well suited
for training pattern parallel implementations where communication
costs are critical.


\subsection{Backpropagation with Weight Decay}
\index{Backpropagation with Weight Decay}
\index{Weight Decay}
\label{bpwd}
Weight Decay was introduced by P. Werbos (\cite{Werbos88}). It
decreases the weights of the links while training them with
backpropagation. In addition to each update of a weight by
backpropagation, the weight is decreased by a part $d$ of its old
value. The resulting formula is
\[
\Delta w_{ij} (t + 1) = \eta\, \delta_j\, o_i - d\, w_{ij}(t)
\]

The effect is similar to the pruning algorithms (see chapter
\ref{Pruning}). Weights are driven to zero unless reinforced by
backpropagation. For further information, see \cite{Schreiner94}.

\section{Quickprop}
\index{Quickprop}

One method to speed up the learning is to use information about the
curvature of the error surface. This requires the computation of the
second order derivatives of the error function. Quickprop assumes the
error surface to be locally quadratic and attempts to jump in
one step from the current position directly into the minimum of the
parabola.

Quickprop \cite{Fahlma88} computes the derivatives in the direction of
each weight. After computing the first gradient with regular
backpropagation, a direct step to the error minimum is attempted by
\begin{displaymath}
  \Delta(t+1) w_{ij} = \frac{S(t+1)}{S(t)-S(t+1)} \Delta(t) w_{ij} 
\end{displaymath}

where:

\begin{tabular}{ll}
  $w_{ij}$      & weight between units i and j\\
  $\Delta(t+1)$ & actual weight change\\
  $S(t+1)$      & partial derivative of the error function by $w_{ij}$\\
  $S(t)$        & the last partial derivative\\
\end{tabular}                                                    


\section{RPROP}
\index{Algorithm!RPROP}
\index{RPROP}

\subsection{Changes in Release 3.3}
The implementation of Rprop has been changed in two ways: First, the
implementation now follows a slightly modified adaptation
scheme. Essentially, the backtracking step is no longer performed, if
a jump over a minimum occurred.  Second, a weight-decay term is
introduced. The weight-decay parameter $\alpha$ (the third learning
parameter) determines the relationship of two goals, namely to reduce
the output error (the standard goal) and to reduce the size of the
weights (to improve generalization).  The composite error function is:
\[E = \sum (t_i - o_i)^2 + 10^{-\alpha} \sum w_{ij}^2 \]

{\em Important:} Please note that the weight decay parameter $\alpha$
denotes the exponent, to allow comfortable input of very small
weight-decay.  A choice of the third learning parameter $\alpha = 4$
corresponds to a ratio of weight decay term to output error of
$1:10000 (1:10^4)$.

\subsection{General Description}
Rprop stands for '{\bf R}esilient back{\bf prop}agation' and is a
local adaptive learning scheme, performing supervised batch learning
in multi-layer perceptrons. For a detailed discussion see also
\cite{Riedmi93c}, \cite{RieBra93a}. 
The basic principle of Rprop is to eliminate the harmful influence of
the size of the partial derivative on the weight step. As a
consequence, only the sign of the derivative is considered to indicate
the {\em direction} of the weight update.  The {\em size} of the
weight change is exclusively determined by a weight-specific,
so-called 'update-value' $\triangle_{ij}^{(t)}$:

\noindent
\begin{eqnarray}
 \label{man} \triangle w_{ij}^{(t)} = \left\{ \begin{array}{r@{\quad,\quad}l}
                    -\triangle_{ij}^{(t)} & \mbox{if } \frac{\partial E}{\partial w_{ij}}^{(t)} > 0
   \\
                    +\triangle_{ij}^{(t)} & \mbox{if } \frac{\partial E}{\partial w_{ij}}^{(t)} < 0
   \\
                    0 & \mbox{else }
                   \end{array} \right.
\end{eqnarray}
where $\frac{\partial E}{\partial w_{ij}}^{(t)}$ denotes the summed gradient information
over all patterns of the pattern set ('batch learning').

It should be noted, that by replacing the $\triangle_{ij}(t)$ 
by a constant update-value $\triangle$, 
equation (\ref{man}) yields the 
so-called 'Manhattan'-update rule.

The second step of Rprop learning is to determine the new
update-values $\triangle_{ij}(t)$. This is based on a sign-dependent adaptation
process.

\begin{eqnarray} 
 \triangle_{ij}^{(t)} = \left\{ \begin{array}{r@{\quad,\quad}l} \eta^+ *
\triangle_{ij}^{(t-1)} & \mbox{if } \frac{\partial E}{\partial w_{ij}}^{(t-1)} * \frac{\partial E}{\partial w_{ij}}^{(t)} >0 \\
\eta^- * \triangle_{ij}^{(t-1)} & \mbox{if } \frac{\partial E}{\partial w_{ij}}^{(t-1)} *
\frac{\partial E}{\partial w_{ij}}^{(t)} <0 \\ \triangle_{ij}^{(t-1)} & \mbox{else} \end{array}
\right.
\end{eqnarray}
\[\mbox{where } 0 < \eta^- < 1 < \eta^+ \]

In words, the adaptation-rule works as follows: Every time the partial
derivative of the corresponding weight $w_{ij}$ changes its sign,
which indicates that the last update was too big and the algorithm has
jumped over a local minimum, the update-value $\triangle_{ij}^{(t)}$
is decreased by the factor $\eta^-$.  If the derivative retains its
sign, the update-value is slightly increased in order to accelerate
convergence in shallow regions.  Additionally, in case of a change in
sign, there should be no adaptation in the succeeding learning
step. In practice, this can be achieved by setting $\frac{\partial
E}{\partial w_{ij}}^{(t-1)} := 0$ in the above adaptation rule (see
also the description of the algorithm in the following section).

In order to reduce the number of freely adjustable parameters, 
often leading to a tedious search in parameter space, the increase and
decrease factor are set to fixed values ($\eta^- := 0.5, \eta^+ = 1.2$).

For Rprop tries to adapt its learning process to the topology of the
error function, it follows the principle of 'batch learning' or
'learning by epoch'.  That means, that weight-update and adaptation
are performed after the gradient information of the whole pattern set
is computed.

\subsection{Parameters}
The Rprop algorithm takes three parameters: the initial update-value
$\triangle_0$, a limit for the maximum step size, $\triangle_{max}$,
and the weight-decay exponent $\alpha$ (see above).

When learning starts, all update-values are set to an initial value
$\triangle_0$.  Since $\triangle_0$ directly determines the size of the first
weight step, it should be chosen according to the initial values of
the weights themselves, for example $\triangle_0 = 0.1$ (default setting).
The choice of this value is rather uncritical, for it is adapted as
learning proceeds.

In order to prevent the weights from becoming too large, the maximum
weight-step determined by the size of the update-value, is limited.
The upper bound is set by the second parameter of Rprop, $\triangle_{max}$. The
default upper bound is set somewhat arbitrarily to $\triangle_{max} = 50.0$.
Usually, convergence is rather insensitive to this parameter as well.
Nevertheless, for some problems it can be advantageous to allow only
very cautious (namely small) steps, in order to prevent the algorithm
getting stuck too quickly in suboptimal local minima.
The minimum step size is constantly fixed to $\triangle_{min} = 1e^{-6}$.


\section{Backpercolation}
\index{Backpercolation}

Backpercolation 1 (Perc1) is a learning algorithm for feedforward
networks.  Here the weights are not changed according to the error of
the output layer as in backpropagation, but according to a unit error
that is computed separately for each unit. This effectively reduces
the amount of training cycles needed.

The algorithm consists of five steps:

\begin{enumerate}
\item A pattern is propagated through the network and the global error
is computed.

\item The gradient $\delta$ is computed and propagated back through
the hidden layers as in backpropagation.

\item The error $\epsilon$ in the activation of each hidden neuron is
computed. This error specifies the value by which the output of this
neuron has to change in order to minimize the global error $Err$.

\item All weight parameters are changed according to $\epsilon$.

\item If necessary, an adaptation of the error magnifying parameter
$\lambda$ is performed once every learning epoch.
\end{enumerate}

The third step is divided into two phases: First each neuron receives
a message $\Delta\mu$, specifying the proposed change in the
activation of the neuron (message creation - MCR). Then each neuron
combines the incoming messages to an optimal compromise, the internal
error $\epsilon$ of the neuron (message optimization - MOP). The MCR
phase is performed in forward direction (from input to output), the
MOP phase backwards.

The internal error $\epsilon_k$ of the output units is defined as
$\epsilon_k \ = \ \lambda (d_k-\phi_k)$, where $\lambda$ is the global
error magnification parameter.


Unlike backpropagation Perc1 does not have a learning parameter.
Instead it has an error magnification parameter $\lambda$. This
parameter may be adapted after each epoch, if the total mean error
of the network falls below the threshold value $\theta$.

When using backpercolation with a network in SNNS the initialization
function {\tt Random\_\-Weights\_\-Perc} and the activation function {\tt
Act\_TanH\_Xdiv2} should be used.



\section{Counterpropagation}
\index{Counterpropagation}

\subsection{Fundamentals}
Counterpropagation was originally proposed as a pattern-lookup system
that takes advantage of the parallel architecture of neural networks.
Counterpropagation is useful in pattern mapping and pattern
completion applications and can also serve as a sort of bidirectional
associative memory.

When presented with a pattern, the network classifies that pattern by
using a learned reference vector. The hidden units play a key role in
this process, since the hidden layer performs a competitive
classification to group the patterns. Counterpropagation works best on
tightly clustered patterns in distinct groups.

Two types of layers are used: The hidden layer is a Kohonen layer with
competitive units that do unsupervised learning; the output layer is
a Grossberg layer, which is fully connected with the hidden layer
and is not competitive.

When trained, the network works as follows. After presentation of a
pattern in the input layer, the units in the hidden layer sum their
inputs according to
\begin{eqnarray*}
       \mbox{net}_{j} & = & \sum_{i} w_{ij} o_{i}
\end{eqnarray*}
and then compete to respond to that input pattern. The unit with the
highest net input wins and its activation is set to 1 while all others
are set to 0.
After the competition, the output layer does a weighted sum on the
outputs of the hidden layer. 
\begin{eqnarray*}
        a_{k} \; = \; \mbox{net}_{k} & = & \sum_{j} w_{jk} o_{j} 
\end{eqnarray*}

Let c be the index of the winning hidden layer neuron. Since $o_{c}$
is the only nonzero element in the sum, which in turn is equal to one,
this can be reduced to
\begin{eqnarray*}
        a_{k} & = & w_{ck}  
\end{eqnarray*}
Thus the winning hidden unit activates a pattern in the output layer.

During training, the weights are adapted as follows:
\begin{enumerate}

\item A winner of the competition is chosen in response to an input pattern.

\item The weights between the input layer and the winner are
adjusted according to
\begin{eqnarray*}
        w_{ic}(t+1) & = &  w_{ic}(t) + \alpha(o_{i} - w_{ic}(t))
\end{eqnarray*}
All the other weights remain unchanged.

\item The output of the network is computed and compared to the target
pattern. 

\item The weights between the winner and the output layer are updated
according to
\begin{eqnarray*}
        w_{ck}(t+1) & = &  w_{ck}(t) + \beta(o_{k} - w_{ck}(t))
\end{eqnarray*}
All the other weights remain unchanged.
\end{enumerate}

\subsection{Initializing Counterpropagation}
\label{CountPropInit}

For Counterpropagation networks three initialization functions are
available: CPN\_Rand\_\-Pat, CPN\_Weights\_v3.2, and CPN\_Weights\_v3.3.
See section \ref{InitFuncs} for a detailed description of these
functions.

{\bf Note:}\\
In SNNS versions 3.2 and 3.3 there was only the initialization
function {\tt CPN\_Weights} available. Although it had the same name,
there was a significant difference between the two. The older version,
still available now as {\tt CPN\_Weights\_v3.2} selected its values
from the hyper{\bf cube} defined by the two initialization parameters.
This resulted in an uneven distribution of these values after they had
been normalized, thereby biasing the network towards a certain
(unknown) direction. The newer version, still available now as {\tt
  CPN\_Weights\_v3.3} selected its values from the hyper{\bf sphere}
defined by the two initialization parameters. This resulted in an even
distribution of these values after they had been normalized. However
it had the disadvantage of having an exponential time complexity,
thereby making it useless for networks with more than about 15 input
units. The influence of the parameters on these two functions is given
below.

Two parameters are used which represent the minimum (a) and maximum
(b) of the range out of which initial values for the second
(Grossberg) layer are selected at random. The vector $w_i$ of weights
leading to unit $i$ of the Kohonen layer are initialized as normalized
vectors (length 1) drawn at random from part of a hyper-sphere
(hyper-cube). Here, min and max determine which part of the
hyper body is used according to table~\ref{ini0}.

\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c|c||l|}\hline
min (a)    & max (b)    & vectors out of \ldots \\\hline
$a \geq 0$ & $b \geq 0$ & positive sector \\
$a \geq 0$ & $b < 0$    & whole hyper-sphere \\
$a < 0 $   & $b \geq 0$ & whole hyper-sphere \\
$a < 0 $   & $b < 0$    & negative sector \\\hline
\end{tabular}
\end{center}
\caption{Influence of minimum and maximum on the initialization of weight
vectors for CPN and SOM.}\label{ini0}
\end{table}


\subsection{Counterpropagation Implementation in SNNS}
To use Counterpropagation in SNNS the following functions and
variables have to be selected.

One of the above mentioned initialization functions, the update function
{\tt CPN\_Order}, and the learning function {\tt Counterpropagation}.
The activation function of the units may be set to any of the
sigmoidal functions available in SNNS.


\section{Dynamic Learning Vector Quantization (DLVQ)} 
\index{DLVQ}

\subsection{DLVQ Fundamentals}
The idea of this algorithm is to find a natural grouping in a set of
data (\cite{Schuer92}, \cite{Duda88}.  Every data vector is associated
with a point in a $d$-dimensional data space. The hope is that the
vectors $\vec{x}$ of the same class form a cloud or a cluster in data
space. The algorithm presupposes that the vectors $\vec{x}$ belonging
to the same class $w_{i}$ are distributed normally with a mean vector
$\vec{\mu_{i}}$, and that all input vectors are normalized.  To
classify a feature vector $\vec{x}$ measure the Euclidian distance
$||\vec{\mu}-\vec{x}||^2$ from $\vec{x}$ to all other mean vectors
$\vec{\mu}$ and assign $\vec{x}$ to the class of the nearest mean. But
what happens if a pattern $\vec{x_{A}}$ of class $w_{A}$ is assigned
to a wrong class $w_{B}$? Then for this wrong classified pattern the
two mean vectors $\vec{\mu_{A}}$ and $\vec{\mu_{B}}$ are moved or
trained in the following way:

\begin{itemize}
\item The reference vector $\vec{\mu_{A}}$ which the wrong classified 
      pattern belongs to, and which is the nearest neighbor to this pattern, 
      is moved a little bit towards this pattern.
\item The mean vector $\vec{\mu_{B}}$, to which a pattern of class $w_{A}$ is 
       assigned wrongly, is moved away from it.
\end{itemize} 

The vectors are moved using the rule:
\begin{eqnarray*}
w_{ij} = w_{ij} + \eta(o_{i} - w_{ij}).
\end{eqnarray*}
where $w_{ij}$ is the weight\footnote{Every mean vector $\vec{\mu}$ of
a class is represented by a class unit. The elements of these vectors
are stored in the weights between class unit and the input units.}
between the output $o_{i}$ of a input unit $i$ and a output unit $j$.
$\eta$ is the learning parameter. By choosing it less or greater than
zero, the direction of movement of a vector can be influenced.

The DLVQ algorithm works in the following way:
\begin{enumerate}
\item Load the (normalized) training data, and calculate for every class the
      mean vector $\mu$. Initialize the net with these vectors. This means:
      Generate a unit for every class and initialize its weights with the
      corresponding values. 
\item Now try to associate every pattern in the training set with a 
      reference vector. If a trainings vector $\vec{x}$ of a class $w_{A}$
      is assigned to a class $w_{B}$ then do the following: 
      \begin{enumerate}
      \item Move the vector $\vec{\mu_{A}}$ which is nearest to $\vec{x_{A}}$ 
            in its direction.
      \item Move the mean vector $\vec{\mu_{B}}$, to which $\vec{x_{A}}$ 
            is falsely assigned to away from it.  
      \end{enumerate}
      Repeat this procedure until the number of correctly classified vectors
      no longer increases.
\item Now calculate, from the vectors of a class $w_{A}$ associated
      with a wrong class $w_{B}$, a new prototype vector $\mu_{A}$. For every 
      class, choose one of the new mean vectors and add it to the
      net. Return to step 2.   
\end{enumerate}  

\subsection{DLVQ in SNNS}
To start DLVQ, the learning function {\tt DLVQ}, the
update function {\tt DLVQ\_\-Update}, and the init function {\tt
DLVQ\_Weights} have to be selected in the corresponding menus. The
init functions of {\tt DLVQ} differ a little from the normal
function: if a DLVQ net is initialized, all hidden units are deleted.

As with learning rules CC and RCC the text field {\tt CYCLE} in
the control panel does {\bf not} specify the number of learning cycles.
This field is used to specify the maximal number of class units to be
generated for each class during learning. The number of learning
cycles is entered as the third parameter in the control panel (see below).

\begin{enumerate}
\item $\eta^{+}$: learning rate, specifies the step width of the mean
vector $\vec{\mu_{A}}$, which is nearest to a pattern $\vec{x_{A}}$,
towards this pattern. Remember that $\vec{\mu_{A}}$ is moved only, if
$\vec{x_{A}}$ is not assigned to the correct class $w_{A}$. A typical
value is 0.03.

\item $\eta^{-}$: learning rate, specifies the step width of a mean
vector $\vec{\mu_{B}}$, to which a pattern of class $w_{A}$ is falsely
assigned to, away from this pattern. A typical value is 0.03. Best
results can be achieved, if the condition $\eta^{+} = \eta^{-}$ is
satisfied.

\item Number of cycles you want to train the net before additive mean
vectors are calculated.
\end{enumerate}

If the topology of a net fits to the DLVQ architecture SNNS will order
the units and layers from left to right independent in the following way:
input layer, hidden layer output layer.  The hidden layer itself is
ordered by classes.

The output layer must consist of only one unit. At the start of the
learning phase it does not matter whether the output layer and the
input layer are connected.  If hidden units exist, they are fully
connected with the input layer. The links between these layers contain
the values of the the mean vectors.  The output layer and the hidden
layer are fully connected. All these links have the value 1 assigned.

\begin{figure}[t]
  \begin{center}
  \begin{minipage}{\textwidth}
    \screendump{0.8}{nn_models/dlvqnet.ps}
  \end{minipage}
  \end{center}
\caption{Topology of a net which was trained with DLVQ.}
\label{dlvqnet}
\end{figure}


The output pattern contains information on which class the input
pattern belongs to. The lowest class must have the name 0. If there are
$n$ classes, the n-th class has the name $n-1$. If these conditions are
violated, an error occurs. Figure \ref{dlvqnet} shows the topology of a
net. In the bias of every class unit its class name is stored. It can be
retrieved by clicking on a class unit with right mouse button.

{\bf Note:} In the first implementation of DLVQ the input patterns
were automatically normalized by the algorithm. This step was
eliminated, since is produced undesired behavior in some cases. Now
the user has to take all necessary steps to normalize the input
vectors correctly before loading them into SNNS.

\subsection{Remarks}

This algorithm was developed in the course of a masters thesis without
knowledge of the original LVQ learning rules (\cite{Koetal91}). Only
later we found out that we had developed a new LVQ algorithm: It
starts with the smallest possible number of hidden layers and adds new
hidden units only when needed. Since the algorithm generates the
hidden layer dynamically during the learning phase, it was called
dynamic LVQ (DLVQ).

It is obvious that the algorithm works only if the patterns belonging 
to the same class have some similarities. Therefore the algorithm best fits 
classification problems such as recognition of patterns, digits, and so on.
This algorithm succeeded in learning 10000 digits with a resolution 
of $16\times16$ pixels. Overall the algorithm generated 49
hidden units during learning. 



\section{Backpropagation Through Time (BPTT)}
\index{Backpropagation through time}
\index{Algorithm!BPTT}
\index{BPTT}
\index{Algorithm!BBPTT}
\index{BBPTT}
\index{Algorithm!QPTT}
\index{QPTT}

This is a learning algorithm for recurrent networks that are updated
in discrete time steps (non-fixpoint networks). These networks may
contain any number of feedback loops in their connectivity graph. The
only restriction in this implementation is that there may be no
connections between input units\footnote{This case may be transformed
into a network with an additional hidden unit for each input unit and
a single connection with unity weight from each input unit to its
corresponding hidden unit.}.  The gradients of the weights in the
recurrent network are approximated using an feedforward network with a
fixed number of layers.  Each layer $t$ contains all activations
$a_i(t)$ of the recurrent network at time step $t$. The highest layer
contains the most recent activations at time $t=0$. These activations
are calculated synchronously, using only the activations at $t=1$ in
the layer below.  The weight matrices between successive layers are
all identical. To calculate an exact gradient for an input pattern
sequence of length $T$, the feedforward network needs $T+1$ layers if
an output pattern should be generated after the last pattern of the
input sequence. This transformation of a recurrent network into a
equivalent feedforward network was first described in
\cite{Minsky69}, p. 145 and the application of backpropagation
learning to these networks was introduced in \cite{Rum862}. 


To avoid deep networks for long sequences, it is possible to use only
a fixed number of layers to store the activations back in time. This
method of {\it truncated backpropagation through time} is described in
\cite{Zipser90} and is used here. An improved feature in this
implementation is the combination with the quickprop algorithm by
\cite{Fahlma88} for weight adaption. The number of additional copies
of network activations is controlled by the parameter {\tt backstep}.
Since the setting of {\tt backstep} virtually generates a hierarchical
network with {\tt backstep} $+ 1$ layers and error information during
backpropagation is diminished very rapidly in deep networks, the
number of additional activation copies is limited by {\tt backstep}
$\le 10$.


There are three versions of backpropagation through time available:

\begin{description}

\item[BPTT:] Backpropagation through time with online-update.\\ 
The gradient for each weight is summed over {\tt backstep} copies
between successive layers and the weights are adapted using the
formula for backpropagation with momentum term after each pattern. The
momentum term uses the weight change during the previous pattern. Using
small learning rates {\tt eta}, {\tt BPTT} is especially useful to
start adaption with a large number of patterns since the weights are
updated much more frequently than in batch-update.

\item[BBPTT:] Batch backpropagation through time.\\
The gradient for each weight is calculated for each pattern as in
{\tt BPTT} and then averaged over the whole training set. The momentum
term uses update information closer to the true gradient than in {\tt
BPTT}.  

\item[QPTT:] Quickprop through time.\\
The gradient in quickprop through time is calculated as in {\tt
BBPTT}, but the weights are adapted using the substantially more
efficient quickprop-update rule.

\end{description}

A recurrent network has to start processing a sequence of patterns
with defined activations. All activities in the network may be set to
zero by applying an input pattern containing only zero values. If such
all-zero patterns are part of normal input patterns, an extra input
unit has to be added for reset control. If this reset unit is set to
$1$, the network is in the free running mode. If the reset unit {\it
and} all normal input units are set to $0$, all activations in the
network are set to $0$ and all stored activations are cleared as well.

The processing of an input pattern $I(t)$ with a set of non-input
activations $a_i(t)$ is performed as follows:

\begin{enumerate}
\item The input pattern $I(t)$ is copied to the input units to become a
subset of the existing unit activations $a_i(t)$ of the whole net.

\item If $I(t)$ contains only zero activations, all activations
$a_i(t+1)$ and all stored activations $a_i(t), a_i(t-1), \ldots, a_i(t
- \mbox{ {\tt backstep}})$ are set to $0.0$.
 
\item All activations $a_i(t+1)$ are calculated synchronously using
the activation function and activation values $a_i(t)$.

\item During learning, an output pattern $O(t)$ is always compared with
the output subset of the {\it new} activations $a_i(t+1)$.

\end{enumerate}

Therefore there is exactly {\it one} synchronous update step between
an input and an output pattern with the same pattern number.

If an input pattern has to be processed with more than one network
update, there has to be a delay between corresponding input and output
patterns.  If an output pattern $o^P$ is the $n$-th pattern after an
input pattern $i^P$, the input pattern has been processed in $n+1$
update steps by the network.  These $n+1$ steps may correspond to $n$
hidden layers processing the pattern or a recurrent processing path
through the network with $n+1$ steps. Because of this pipelined
processing of a pattern sequence, the number of hidden layers that may
develop during training in a fully recurrent network is influenced by
the delay between corresponding input and output patterns. If the
network has a defined hierarchical topology without shortcut
connections between $n$ different hidden layers, an output pattern
should be the $n$-th pattern after its corresponding input pattern in
the pattern file.

An example illustrating this relation is given with the delayed XOR
network in the network file {\tt xor-rec.net} and the pattern files {\tt
xor-rec1.pat} and {\tt xor-rec2.pat}. With the patterns {\tt
xor-rec1.pat}, the task is to compute the XOR function of the
previous input pattern.  In {\tt xor-rec2.pat}, there is a delay of
2 patterns for the result of the XOR of the input pattern. Using a
fixed network topology with shortcut connections, the BPTT learning
algorithm develops solutions with a different number of processing
steps using the shortcut connections from the first hidden layer to
the output layer to solve the task in {\tt xor-rec1.pat}. To map the
patterns in {\tt xor-rec2.pat} the result is first calculated in the
second hidden layer and copied from there to the output layer during
the next update step\footnote{If only an upper bound $n$ for the
number of processing steps is known, the input patterns may consist of
windows containing the current input pattern together with a sequence
of the previous $n-1$ input patterns.  The network then develops a
focus to the sequence element in the input window corresponding to the
best number of processing steps.}.

The update function {\tt BPTT-Order} performs the synchronous update
of the network and detects reset patterns.  If a network is tested
using the \fbox{TEST} button in the control panel, the internal
activations and the output activation of the output units are first
overwritten with the values in the target pattern, depending on the
setting of the button \fbox{SHOW}. To provide correct activations on
feedback connections leading out of the output units in the following
network update, all output activations are copied to the units initial
activation values {\tt i\_act} after each network update and are
copied back from {\tt i\_act} to {\tt out} before each update.  The
non-input activation values may therefore be influenced before a
network update by changing the initial activation values {\tt i\_act}.

If the network has to be reset by stepping over a reset pattern with
the \fbox{TEST} button, keep in mind that after clicking \fbox{TEST},
the pattern number is increased first, the new input pattern is copied
into the input layer second, and then the update function is called.
So to reset the network, the current pattern must be set to the pattern
directly preceding the reset pattern.


\section{The Cascade Correlation Algorithms}
\index{Cascade Correlation}
\index{Recurrent Cascade Correlation}
\index{Algorithm!Cascade Correlation}

Two cascade correlation algorithms have been implemented in SNNS,
Cascade-Correlation and recurrent Cascade-Correlation. Both learning
algorithms have been developed by Scott Fahlman (\cite{FahLeb91},
\cite{HoeFahl91}, \cite{Fahl91}). Strictly speaking the cascade
architecture represents a kind of meta algorithm, in which usual
learning algorithms like Backprop, Quickprop or Rprop are embedded.
Cascade-Correlation is characterized as a constructive learning rule.
It starts with a minimal network, consisting only of an input and an
output layer. Minimizing the overall error of a net, it adds step by
step new hidden units to the hidden layer.

Cascade-Correlation is a supervised learning architecture which builds
a near minimal multi-layer network topology.  The two advantages of
this architecture are that there is no need for a user to worry about
the topology of the network, and that Cascade-Correlation learns much
faster than the usual learning algorithms.

\subsection{Cascade-Correlation (CC)}

\subsubsection{The Algorithm}

Cascade-Correlation (CC) combines two ideas: The first is the cascade
architecture, in which hidden units are added only one at a time and
do not change after they have been added. The second is the learning
algorithm, which creates and installs the new hidden units. For each
new hidden unit, the algorithm tries to maximize the magnitude of the
correlation between the new unit's output and the residual error
signal of the net.

The algorithm is realized in the following way:

\begin{enumerate}
  \item CC starts with a minimal network consisting only of an input
and an output layer. Both layers are fully connected.

  \item Train all the connections ending at an output unit with a usual
learning algorithm until the error of the net no longer decreases.

  \item Generate the so-called candidate units. Every candidate
unit is connected with all input units and with all existing hidden
units.  Between the pool of candidate units and the output units there
are no weights.  

  \item Try to maximize the correlation between the activation of
the candidate units and the residual error of the net by training all
the links leading to a candidate unit.  Learning takes place with an
ordinary learning algorithm. The training is stopped when the
correlation scores no longer improves.

  \item Choose the candidate unit with the maximum correlation,
freeze its incoming weights and add it to the net. To change the
candidate unit into a hidden unit, generate links between the selected
unit and all the output units. Since the weights leading to the new
hidden unit are frozen, a new permanent feature detector is obtained.
Loop back to step 2.
\end{enumerate}

This algorithm is repeated until the overall error of the net falls below
a given value.  Figure \ref{cascade net} shows a net after 3 hidden units
have been added.

\begin{figure}[htbp]
\begin{center}
  \begin{minipage}{\textwidth}
    \screendump{0.6}{nn_models/cascade_net.ps}
  \end{minipage}
\caption{A neural net trained with cascade-correlation after 3 hidden units
have been added. The vertical lines add all incoming activations. Connections
with white boxes are frozen. The black connections are trained
repeatedly.}
\label{cascade net} 
\end{center}
\end{figure}


\subsubsection{Mathematical Background}

The training of the output units tries to minimize the sum-squared
error $E$:

\begin{eqnarray*}
E=\sum_{p}\frac{1}{2}\sum_{o}(y_{po}-t_{po})^{2}
\end{eqnarray*}

where $t_{po}$ is the desired and $y_{po}$ is the observed output of the 
output unit $o$ for a pattern $p$. The error $E$ is minimized by gradient
decent using

\begin{eqnarray*}
e_{po} & = & (y_{po}-t_{po})f_{p}'(net_{o})  \nonumber      \\
\frac{\partial E}{\partial w_{io}} & = & \sum_{p}e_{po} I_{ip}, 
\label{formel}
\end{eqnarray*}

where $f'_{p}$ is the derivative of an activation function of a output unit 
$o$ and $I_{ip}$ is the value of an input unit or a hidden unit $i$ 
for a pattern $p$. $w_{io}$ denominates the connection between an input or
hidden unit $i$ and an output unit $o$. 

After the training phase the candidate units are adapted, so that the
correlation $C$ between the value $y_{po}$ of a candidate unit and the
residual error $e_{po}$ of an output unit becomes maximal. The
correlation is given by Fahlman with:

\begin{eqnarray*}
C & =
&\sum_{o}\left|\sum_{p}(y_{po} - \bar{y_{o}})(e_{po} - \bar{e_{o}})\right| \nonumber \\
  & = &\sum_{o}\left|
        \sum_{p} y_{po} e_{po} - 
\bar{e_{o}}\sum_{p}y_{po} \right| \nonumber \\
  & = &\sum_{o}\left| \sum_{p} y_{po} (e_{po}- \bar{e_{o}}) \right|,
\end{eqnarray*}

where $\bar{y_{o}}$ is the average activation of a candidate unit and
$\bar{e_{o}}$ is the average error of an output unit over all patterns
$p$. The maximization of C proceeds by gradient ascent using

\begin{eqnarray*}
\delta_{p} & = &\sum_{o}\sigma_{o}(e_{po} - \bar{e_{j}})f_{p}' \nonumber \\
\frac{\partial C}{\partial w_{i}} & = & \sum_{p} \delta_{p}I_{pi},
\end{eqnarray*}

where $\sigma_{o}$ is the sign of the correlation between the candidate unit's
output and the residual error at output $o$.


\subsection{Pruned-Cascade-Correlation (PCC)}
\label{pcc}
\index{PCC}

\subsubsection{The Algorithm}

The aim of Pruned-Cascade-Correlation (PCC) is to minimize the {\it
expected} test set error, instead of the actual training error
\cite{Weh94}. PCC tries to determine the optimal number of hidden
units and to remove unneeded weights after a new hidden unit is
installed. As pointed out by Wehrfritz, selection criteria or a
hold-out set, as it is used in ``stopped-learning'', may be applied to
digest away unneeded weights. In this release of SNNS, however, only
selection criteria for linear models are implemented.

The algorithm works as follows (CC steps are printed italic):

\begin{enumerate}
\item{\it Train the connections to the output layer}
\item{Compute the selection criterion}
\item{\it Train the candidates}
\item{\it Install the new hidden neuron}
\item{Compute the selection criterion}
\item{Set each weight of the last inserted unit to zero and compute
    the selection criterion; if there exists a weight, whose removal
    would decrease the selection criterion, remove the link, which
    decreases the selection criterion {\bf most}. Goto step 5 until a
    further removal would increase the selection criterion.}
\item{Compute the selection criterion; if it is greater than the one,
    computed before inserting the new hidden unit, notify the user
    that the net is getting too big.}
\end{enumerate}

\subsubsection{Mathematical Background}

In this release of SNNS, three model selection criteria are
implemented: the Schwarz's Bayesian criterion (SBC), Akaikes information
criterion (AIC) and the conservative mean square error of prediction (CMSEP).
The {\it SBC}, the default criterion, is more conservative compared to
the {\it AIC}. Thus, pruning via the {\it SBC} will produce smaller networks
than pruning via the {\it AIC}.
Be aware that both {\it SBC} and {\it AIC} are selection criteria for {\it
linear} models, whereas the {\it CMSEP} does not rely on any statistical
theory, but happens to work pretty well in an application. These
selection criteria for linear model can sometimes directly be applied
to nonlinear models, if the sample size is large. 



\subsection{Recurrent Cascade-Correlation (RCC)}

\subsubsection{The Algorithm}

Recurrent Cascade-Correlation (RCC) is a recurrent version of
Cascade-Correlation and can be used to train recurrent neural nets
(\cite{Elman90}).

Recurrent nets have some features that distinguish them from normal
neural networks.  For example they can be used to represent time
implicitly rather than explicitly. One of
the most commonly known architectures of recurrent neural nets is the
Elman model, which assumes that the network operates in discrete
time steps. The outputs of the network's hidden units at a time $t$ are
fed back for use as additional network inputs at time $t+1$. To store
the output of the hidden units Elman introduced {\it context units},
which represent a kind of short-term memory (see fig.~\ref{elman
net}). To integrate the Elman model into the cascade architecture some
changes are necessary: The hidden units' values are no longer fed
back to all other hidden units. Instead every hidden unit has only one
self recurrent link as shown in figure \ref{rcc net}. This self
recurrent link is trained along with the candidate unit's other input
weights to maximize the correlation. When the candidate unit is added
to the active network as hidden unit, the recurrent link is frozen
along with all other links.

\begin{figure}[htbp]
  \begin{minipage}[h]{7.0cm}
      \screendump{0.7}{nn_models/elman_net.ps}
      \caption{The Elman architecture of a recurrent neural net}
      \label{elman net}
  \end{minipage}
  \hfill
  \begin{minipage}[h]{7.0cm}
    \centerline{\screendump{0.7}{nn_models/rcc_net.ps}}
    \caption{RCC architecture of a recurrent neural net.}
    \label{rcc net}
  \end{minipage}
\end{figure}

\subsubsection{Mathematical Background}

The output of a recurrent unit $r$ is given by:

\begin{eqnarray*}
V(t) & = & f_{act}\left(\sum_{i} I_{i}(t)w_{ir} + V(t-1)w_{s} \right),
\label{recact}
\end{eqnarray*} 

where: \\
\begin{tabular}{ll}
$f_{act}$: & any activation function \\
$w_{ir}$:  & the weight of the connection between the input unit $i$ and 
             the unit $r$ \\
$w_{s}$:   & the value of the self recurrent connection. \\
$I_{i}$:   & output of the input unit $i$ 
\end{tabular}

The derivatives of $V(t)$ with respect to $w_{ir}$ and $w_{s}$ are computed
as follows:

\begin{eqnarray*}
\frac{\partial V}{\partial w_{ir}} & = 
   f'_{act}(t) (I_{i}(t)+w_{s} \frac{\partial V(t-1)}{\partial w_{ir}}) 
\end{eqnarray*}
and
\begin{eqnarray*}
\frac{\partial V}{\partial w_{s}} & = 
   f'_{act}(t) (V(t-1)+w_{s} \frac{\partial V(t-1)}{\partial w_{s}}).
\end{eqnarray*} 

At $t=0$, it is assumed that the unit's previous value and previous
derivatives are all zero.


\subsection{Using the Cascade Algorithms in SNNS}

Networks that make use of the cascade correlation architecture can be
created in SNNS in the same way as all other network types. The
control of the training phase, however, is moved from the control panel
to the special cascade window described below. The control panel is
still used to specify the learning parameters, while the text field
{\tt CYCLE} does {\bf not} specify as usual the number of learning
cycles. This field is used here to specify the maximal number of
hidden units to be generated during the learning phase. The number of
learning cycles is entered in the cascade window.  The learning
parameters for the embedded learning functions Quickprop, Rprop and
Backprop are described in chapter \ref{LearningParameters}.
  
If the topology of a net is specified correctly, the program will
automatically order the units and layers from left to right in the
following way: input layer, hidden layer, output layer, and a 
candidate layer. \footnote{The candidate units are realized as special
units in SNNS.}  The hidden layer is generated with 5 units always
having the same x-coordinate (i.e. above each other on the display).

The cascade correlation control panel and the cascade window (see
fig.~\ref{cascade window}), is opened by clicking the \fbox{\tt
  Cascade} button in the manager panel.  The cascade window is needed
to set the parameters of the learning algorithms CC and RCC. To start
Cascade Correlation, learning function {\tt CC}, update function {\tt
  CC\_Order} and init function {\tt CC\_Weights} in the corresponding
menus have to be selected. Recurrent Cascade-Correlation is started in
the same way, only that this time the functions {\tt RCC, RCC\_Update}
and {\tt RCC\_Weights} have to be selected.  If one of these functions
is left out, a confirmer window with an error message pops up and
learning does not start. The init functions of cascade differ from the
normal init functions: upon initialization of a cascade net all hidden
units are deleted.

\begin{figure}[htbp]
\begin{center}
  \begin{minipage}{\textwidth}
    \screendump{0.4}{nn_models/cascade_window.ps}
  \end{minipage}
\caption{The cascade window}
\label{cascade window}
\end{center}
\end{figure}

The cascade window has the following text fields, buttons and menus:
\begin{itemize}
\item {\tt Global parameters:} 
  \begin{itemize}
    \item {\tt Max. output unit error:} \\
      This value is used as abort condition for the learning algorithms
      CC and RCC. If the error of every single output unit is smaller 
      than the given value learning will be terminated.
    \item {\tt Learning function:} \\
      Here, the learning function used to maximize the covariance or
      to minimize the net error can be selected from a pull down menu. 
      Available learning functions are: {\tt Quickprop}, {\tt Rprop} and {\tt
      Backprop} 
    \item {\tt Print covariance and error:} \\
      If this menu item shows {\tt on}, the development of the error and
      and the covariance of every candidate unit is printed. {\tt off}
      prevents all outputs of the net.
    \item{\tt Prune new hidden unit:\\} This enables
      ``Pruned-Cascade-Correlation''. It defaults to {\tt off}, which
      means do not remove any weights from the new inserted hidden
      unit.
    \item{\tt Minimize:\\} The selection criterion according to which
      PCC tries to minimize. The default selection criterion is the
      ``Schwarz's Bayesian criterion'', other criteria available are
      ``Akaikes information criterion'' and the ``conservative mean
      square error of prediction''.  This option is ignored, unless
      PCC is enabled.
  \end{itemize}
\item {\tt Candidate Parameters:} 
  \begin{itemize}
    \item {\tt Min.~covariance change:} \\
      The covariance must change by at least this fraction of its old 
      value to count as a significant change. If this fraction is not
      reached, learning is halted and the candidate unit with the maximum
      covariance is changed into a hidden unit.
    \item {\tt Candidate patience:} \\
      After this number of steps the program tests whether there is
      a significant change of the covariance. The change is said to be
      significant if it is larger than the fraction given by {\tt
      Min.~covariance change}.
    \item {\tt Max.~no.~of covariance updates:} \\
      The maximum number of steps to calculate the covariance. After reaching
      this number, the candidate unit with the maximum covariance is changed
      to a hidden unit.
    \item {\tt Max. no. of candidate units:} \\
      The maximum number of candidate units trained at once.
    \item {\tt Activation function:} \\
      This menu item makes it possible to choose between different activation
      functions for the candidate units. The functions are: {\tt Act\_Logistic
      Act\_LogSym, Act\_Tanh, Act\_Identity} and {\tt Random}. {\tt
      Random} is not a real activation function. It randomly assigns
      one of the other activation functions to each candidate unit.
      The function {\tt Act\_LogSym} is identical to {\tt Act\_Logistic}, 
      except that it is shifted by $-0.5$ along the y-axis. 
  \end{itemize}
\item {\tt Output Parameters:} 
  \begin{itemize}
    \item {\tt Error change:} \\
          analogous to {\tt Min.~covariance change} 
    \item {\tt Output patience:} \\
          analogous to {\tt Candidate patience}
    \item {\tt Max. no. of epochs:} \\
          analogous to {\tt Max. no. of covariance updates}
  \end{itemize} 
\end{itemize}

The button \framebox{DELETE CAND. UNITS} deletes all candidate units.
In SNNS the candidate units are realized as special units.


\section{Time Delay Networks (TDNNs)}
\index{Time Delay Networks}

\subsection{TDNN Fundamentals} 

Time delay networks (or TDNN for short), introduced by Alex Waibel
(\cite{Wai89}), are a group of neural networks that have a special
topology. They are used for position independent recognition of
features within a larger pattern. A special convention for naming
different parts of the network is used here (see figure~\ref{TD_naming.ps})

\begin{figure}[htbp]
\begin{center}
  \begin{minipage}{\textwidth}
    \screendump{0.4}{nn_models/bn_td_naming_horiz.ps}
  \end{minipage}
\caption{The naming conventions of TDNNs}
\label{TD_naming.ps}
\end{center}
\end{figure}

\begin{itemize}
  \item {\bf Feature: } A component of the pattern to be learned.

  \item {\bf Feature Unit: } The unit connected with the feature to be
learned. There are as many feature units in the input layer of a TDNN
as there are features.

  \item {\bf Delay: } In order to be able to recognize patterns
place or time-invariant, older activation and connection values of the feature
units have to be stored. This is performed by making a copy of the
feature units with all their outgoing connections in each time step,
before updating the original units. The total number of time steps
saved by this procedure is called {\sl delay}. 

  \item {\bf Receptive Field: } The feature units and their delays are
fully connected to the original units of the subsequent layer. These
units are called {\sl receptive field}. The receptive field is
usually, but not necessarily, as wide as the number of feature units;
the feature units might also be split up between several receptive
fields. Receptive fields may overlap in the source plane, but do have
to cover all feature units.

  \item {\bf Total Delay Length: } The length of the layer. It equals
the sum of the length of all delays of the network layers topological
following the current one minus the number of these subsequent layers.

  \item {\bf Coupled Links: } Each link in a receptive field is
reduplicated for every subsequent step of time up to the total delay
length. During the learning phase, these links are treated as a single
one and are changed according to the average of the changes they would
experience if treated separately. Also the units' bias which realizes a
special sort of link weight is duplicated over all delay steps of a
current feature unit. In figure~\ref{TD_naming.ps} only
two pairs of coupled links are depicted (out of 54 quadruples) for
simplicity reasons. 
\end{itemize}

The activation of a unit is normally computed by passing the weighted
sum of its inputs to an activation function, usually a threshold
or sigmoid function. For TDNNs this behavior is modified through the
introduction of delays. Now all the inputs of a unit are each
multiplied by the N delay steps defined for this layer. So a hidden
unit in figure~\ref{TD_naming.ps} would get 6 undelayed input links
from the six feature units, and 7x6 = 48 input links from the seven
delay steps of the 6 feature units for a total of 54 input
connections. Note, that all units in the hidden layer have 54 input
links, but only those hidden units activated at time 0 (at the top
most row of the layer) have connections to the actual feature units.
All other hidden units have the same connection pattern, but shifted
to the bottom (i.e. to a later point in time) according to their
position in the layer (i.e. delay position in time). By building a
whole network of time delay layers, the TDNN can relate inputs in
different points in time or input space.

Training in this kind of network is performed by a procedure similar
to backpropagation, that takes the special semantics of coupled links
into account. To enable the network to achieve the desired behavior, a
sequence of patterns has to be presented to the input layer with the
feature shifted within the patterns. Remember that since each of the
feature units is duplicated for each frame shift in time, the whole
history of activations is available at once. But since the shifted
copies of the units are mere duplicates looking for the same event,
weights of the corresponding connections between the time shifted
copies have to be treated as one. First, a regular forward pass of
backpropagation is performed, and the error in the output layer is
computed. Then the error derivatives are computed and propagated
backward. This yields different correction values for corresponding
connections. Now all correction values for corresponding links are
averaged and the weights are updated with this value.

This update algorithm forces the network to train on time/position
independent detection of sub-patterns. This important feature of TDNNs
makes them independent from error-prone preprocessing algorithms for
time alignment. The drawback is, of course, a rather long,
computationally intensive, learning phase.


\subsection{TDNN Implementation in SNNS}

The original time delay algorithm was slightly modified for
implementation in SNNS, since it requires either variable network
sizes or fixed length input patterns. Time delay networks in SNNS
are allowed no delay in the output layer. This has the following
consequences:

\begin{itemize}
  \item The input layer has fixed size.
  \item Not the whole pattern is present at the input layer at once.
Therefore one pass through the network is not enough to compute all
necessary weight changes. This makes learning more computationally
intensive. 
\end{itemize}

The coupled links are implemented as one physical (i.e. normal) link
and a set of logical links associated with it. Only the physical links
are displayed in the graphical user interface. The bias of all delay
units has no effect. Instead, the bias of the corresponding feature
unit is used during propagation and backpropagation.

\subsubsection*{Activation Function}

For time delay networks the new activation function {\tt
Act\_TD\_Logistic} has been implemented. It is similar to the regular
logistic activation function {\tt Act\_Logistic} but takes care of
the special coupled links. The mathematical notation is again
\begin{displaymath}
        a_{j}(t+1) = \frac{1}{{1 + e^{- \left( \sum_{i} w_{ij} o_{i}(t) 
                                        - \theta_{j} \right) }}}
\end{displaymath}
where $o_{i}$ includes now also the predecessor units along logical
links.

\subsubsection*{Update Function}
The update function {\tt TimeDelay\_Order} is used to propagate
patterns through a time delay network. It's behavior is analogous to
the {\tt Topological\_Order} function with recognition of logical links.

\subsubsection*{Learning Function}
The learning function {\tt TimeDelayBackprop} implements the modified
backpropagation algorithm discussed above. It uses the same learning
parameters as standard backpropagation.


\subsection{Building and Using a Time Delay Network}

In SNNS, TDNNs should be generated only with the tool {\tt BIGNET
(Time Delay)}. This program automatically defines the necessary
variables and link structures of TDNNs. The logical links are not
depicted in the displays and can not be modified with the graphical
editor. Any modifications of the units after the creation of the
network may result in undesired behavior or even system failure!

After the creation of the net, the unit activation function {\tt
Act\_TD\_Logistic}, the update function {\tt TimeDelay\_Order}, and
the learning function {\tt TimeDelayBackprop} have to be assigned in
the usual way.

{\bf NOTE:} Only after the special time delay learning function has
been assigned, will a save of the network also save the special logical
links! A network saved beforehand will lack these links and be useless
after a later load operation. Also using the \fbox{TEST} and
\fbox{STEP} button will destroy the special time delay information
unless the right update function ({\tt TimeDelay\_Order}) has been
chosen.

Patterns must fit the input layer. If the application requires
variable pattern length, a tool to segment these patterns into fitting
pieces has to be applied. Patterns may also be generated with the
graphical user interface. In this case, it is the responsibility of
the user to supply enough patterns with time shifted features for the
same teaching output to allow a successful training.


\section{Radial Basis Functions (RBFs)}
\label{integration}


The following section describes the use of generalized radial basis
functions inside SNNS. First, a brief introduction to the mathematical
background of radial basis functions is given. Second, the special
procedures of initialization and training of neural nets based on
radial basis functions are described. At the end of the chapter a set
of necessary actions to use radial basis functions with a specific
application are given.

\subsection{RBF Fundamentals}
\index{Radial Basis Functions}

The principle of radial basis functions derives from the theory of
functional approximation. Given $N$ pairs $(\vec{x_i},y_i)$ ($\vec{x}
\in \Re^n, y \in \Re$) we are looking for a function $f$ of the form:

\[
f(\vec{x}) = \sum_{i=1}^K c_i h(|\vec{x} - \vec{t_i}|)
\]

$h$ is the radial basis function and $\vec{t_i}$ are the $K$
centers which have to be selected. The coefficients $c_i$ are also
unknown at the moment and have to be computed. $\vec{x_i}$ and
$\vec{t_i}$ are elements of an n--dimensional vector space.

$h$ is applied to the Euclidian distance between each center
$\vec{t_i}$ and the given argument $\vec{x}$. Usually a function $h$
which has its maximum at a distance of zero is used, most often the
Gaussian function. In this case, values of $\vec{x}$ which are equal
to a center $\vec{t}$ yield an output value of 1.0 for the function
$h$, while the output becomes almost zero for larger distances.

The function $f$ should be an approximation of the $N$ given pairs
$(\vec{x_i},y_i)$ and should therefore minimize the following error
function $H$:

\[
H[f] = \sum_{i=1}^N (y_i - f(\vec{x_i}))^2 + \lambda \|P f\|^2
\]

The first part of the definition of $H$ (the sum) is the condition
which minimizes the total error of the approximation, i.e. which
constrains $f$ to approximate the $N$ given points. The second part of
$H$ ( $\|P f\|^2$ ) is a stabilizer which forces $f$ to become as
smooth as possible. The factor $\lambda$ determines the influence of
the stabilizer.

Under certain conditions it is possible to show that a set of
coefficients $c_i$ can be calculated so that $H$ becomes minimal. 
This calculation depends on the centers $\vec{t_i}$ which
have to be chosen beforehand. 

Introducing the following vectors and matrices $\vec{c} = (c_1,
\cdots, c_K)^T, \vec{y} = (y_1, \cdots, y_N)^T$
\[
G = \left( \begin{array}{ccc} 
h(|\vec{x_1}-\vec{t_1}|) & \cdots & h(|\vec{x_1}-\vec{t_K}|) \\
\vdots & \ddots & \vdots \\
h(|\vec{x_N}-\vec{t_1}|) & \cdots & h(|\vec{x_N}-\vec{t_K}|)
\end{array}\right),
\quad
G_\Box = \left( \begin{array}{ccc} 
h(|\vec{t_1}-\vec{t_1}|) & \cdots & h(|\vec{t_1}-\vec{t_K}|) \\
\vdots & \ddots & \vdots \\
h(|\vec{t_K}-\vec{t_1}|) & \cdots & h(|\vec{t_K}-\vec{t_K}|)
\end{array}\right)
\]

the set of unknown parameters $c_i$ can be calculated by the formula:

\[
\vec{c} = ( G^T \cdot G + \lambda G_\Box)^{-1} \cdot G^T \cdot \vec{y}
\]

By setting $\lambda$ to $0$ this formula becomes identical to the
computation of the Moore Penrose inverse matrix, which gives the best
solution of an under-determined system of linear equations. In this
case, the linear system is exactly the one which follows directly from
the conditions of an exact interpolation of the given problem:

\[
f(\vec{x_j}) = \sum_{i=1}^K c_i h(|\vec{x_j} - \vec{t_i}|)
\stackrel{!}{=} y_j \quad , \quad j = 1, \ldots N
\]

The method of radial basis functions can easily be represented by a
three layer feedforward neural network. The input layer consists of n
units which represent the elements of the vector $\vec{x}$. The $K$
components of the sum in the definition of $f$ are represented by the
units of the hidden layer. The links between input and hidden layer
contain the elements of the vectors $\vec{t_i}$. The hidden units
compute the Euclidian distance between the input pattern and the
vector which is represented by the links leading to this unit. The
activation of the hidden units is computed by applying the Euclidian
distance to the function $h$. Figure~\ref{rbf_special_unit} shows the
architecture of the special form of hidden units.

% The following picture was derived from the file
% `./xgui_figs/rbf_unit.fig', that can be edited with xfig.

\begin{figure}[htbp]
\begin{center}
\setlength{\unitlength}{0.0125in}
\begin{picture}(445,230)(0,-10)
\thicklines
\put(200,30){\ellipse{60}{60}}
\put(200,185){\ellipse{60}{60}}
\put(350,115){\ellipse{50}{50}}
\path(15,150)(170,175)
\path(162.421,171.752)(170.000,175.000)(161.784,175.701)
\path(15,30)(180,165)
\path(175.075,158.386)(180.000,165.000)(172.542,161.482)
\path(15,30)(170,30)
\path(162.000,28.000)(170.000,30.000)(162.000,32.000)
\path(15,150)(325,110)
\path(316.810,109.040)(325.000,110.000)(317.322,113.007)
\path(230,185)(330,130)
\path(322.026,132.103)(330.000,130.000)(323.954,135.608)
\path(375,115)(445,115)
\path(437.000,113.000)(445.000,115.000)(437.000,117.000)
\path(15,185)(180,50)
\path(172.542,53.518)(180.000,50.000)(175.075,56.614)
\path(15,150)(170,40)
\path(162.318,42.999)(170.000,40.000)(164.633,46.261)
\path(15,185)(170,185)
\path(162.000,183.000)(170.000,185.000)(162.000,187.000)
\path(230,30)(335,95)
\path(329.251,89.089)(335.000,95.000)(327.145,92.490)
\path(15,30)(330,100)
\path(322.624,96.312)(330.000,100.000)(321.757,100.217)
\path(15,183)(325,118)
\path(316.760,117.684)(325.000,118.000)(317.581,121.599)
\drawline(200,105)(200,105)
\drawline(200,100)(200,100)
\drawline(200,95)(200,95)
\drawline(200,90)(200,90)
\drawline(15,110)(15,110)
\drawline(15,95)(15,95)
\drawline(15,80)(15,80)
\drawline(15,65)(15,65)
\put(0,25){\parbox{0.5cm}{\[x_n\]}}
\put(275,175){\parbox{0.7cm}{\[c_1\]}}
\put(280,40){\parbox{0.5cm}{\[c_K\]}}
\put(400,120){\parbox{0.5cm}{\[o\]}}
\put(175,182){\parbox{1.7cm}{\[h(|\vec{x} - \vec{t_j}|)\]}}
\put(175,27){\parbox{1.7cm}{\[h(|\vec{x} - \vec{t_j}|)\]}}
\put(0,180){\parbox{0.5cm}{\[x_1\]}}
\put(340,115){\parbox{0.7cm}{\[\Sigma\]}}
\put(80,190){\parbox{0.7cm}{\[t_{1,1}\]}}
\put(80,10){\parbox{0.7cm}{\[t_{n,K}\]}}
\put(220,85){\parbox{0.5cm}{\[d_n\]}}
\put(245,140){\parbox{0.5cm}{\[d_1\]}}
\put(0,145){\parbox{0.5cm}{\[x_2\]}}
\put(115,174){\parbox{0.7cm}{\[t_{2,1}\]}}
\put(40,70){\parbox{0.7cm}{\[t_{n,1}\]}}
\put(170,115){\parbox{0.5cm}{\[d_2\]}}
\end{picture}
\caption{The special radial basis unit}
\label{rbf_special_unit}
\end{center}
\end{figure}

The single output neuron gets its input from all hidden neurons. The links
leading to the output neuron hold the coefficients $c_i$. The activation
of the output neuron is determined by the weighted sum of its inputs.

The previously described architecture of a neural net, which realizes
an approximation using radial basis functions, can easily be expanded
with some useful features: More than one output neuron is possible which
allows the approximation of several functions $f$ around the same set
\index{Radial Basis Functions!Activation Function}
of centers $\vec{t_i}$. The activation of the output units can be
calculated by using a nonlinear invertible function $\sigma$ (e.g.\
sigmoid). The bias of the output neurons and a direct connection
between input and hidden layer (shortcut connections) can be used to
improve the approximation quality. The bias of the hidden units can
be used to modify the characteristics of the function $h$. All in all
a neural network is able to represent the following set of
approximations:

\begin{eqnarray*}
o_k(\vec{x}) = \sigma \left( \sum_{j=1}^K c_{j,k} h \left( |\vec{x}
- \vec{t_j}|,p_j \right) + \sum_{i=1}^n d_{i,k} x_i + b_k \right) =
\sigma \left( f_k(\vec{x}) \right) \; , \quad k = 1,\ldots,m 
\end{eqnarray*}

This formula describes the behavior of a fully connected feedforward
net with $n$ input, $K$ hidden and $m$ output neurons.  $o_k(\vec{x})$
is the activation of output neuron $k$ on the input $\vec{x} = x_1,
x_2, \ldots, x_n$ to the input units. The coefficients $c_{j,k}$
represent the links between hidden and output layer. The shortcut
connections from input to output are realized by $d_{i,k}$.  $b_k$ is
the bias of the output units and $p_j$ is the bias of the hidden
neurons which determines the exact characteristics of the function
$h$. The activation function of the output neurons is represented by
$\sigma$.

The big advantage of the method of radial basis functions is the
possibility of a direct computation of the coefficients $c_{j,k}$
(i.e. the links between hidden and output layer) and the bias $b_k$.
This computation requires a suitable choice of centers $\vec{t_j}$
(i.e. the links between input and hidden layer). Because of the lack
of knowledge about the quality of the $\vec{t_j}$, it is recommended
to append some cycles of network training after the direct computation
of the weights. Since the weights of the links leading from the input
to the output layer can also not be computed directly, there must be a
special training procedure for neural networks that uses radial basis
functions.

The implemented training procedure tries to minimize the error $E$ by 
using gradient descent. It is recommended to use different learning rates
for different groups of trainable parameters. The following set of
formulas contains all information needed by the training procedure:

\begin{eqnarray*}
E = \sum_{k=1}^m \left( \sum_{i=1}^N (y_{i,k} - o_k(\vec{x_i}))^2
\right)
\label{a_fehler_formel}
\quad , \quad
\Delta \vec{t_j} = - \eta_1 \frac{\partial E}{\partial \vec{t_j}}
\quad , \quad \Delta p_j = - \eta_2 \frac{\partial E}{\partial p_j}
\end{eqnarray*}

\begin{eqnarray*}
\Delta c_{j,k} = - \eta_3 \frac{\partial E}{\partial c_{j,k}} \quad ,
\quad \Delta d_{i,k} = - \eta_3 \frac{\partial E}{\partial d_{i,k}}
\quad , \quad \Delta b_k = - \eta_3 \frac{\partial E}{\partial b_{k}}
\end{eqnarray*}

It is often helpful to use a momentum term. This term increases the
learning rate in smooth error planes and decreases it in rough error
planes. The next formula describes the effect of a momentum term on
the training of a general parameter $g$ depending on the additional
parameter $\mu$. $\Delta g_{t+1}$ is the change of $g$ during the time
step $t+1$ while $\Delta g_{t}$ is the change during time step $t$:

\begin{eqnarray*}
\Delta g_{t+1} = - \eta \frac{\partial E}{\partial g} + \mu \Delta g_{t}
\end{eqnarray*}

Another useful improvement of the training procedure is the definition
of a maximum allowed error inside the output neurons. This prevents
the network from getting overtrained, since errors that are smaller than
the predefined value are treated as zero. This in turn prevents the
corresponding links from being changed.
 

\subsection{RBF Implementation in SNNS}

\subsubsection{Activation Functions}
\label{RBF_actFuncs}

For the use of radial basis functions, three different activation
functions $h$ have been implemented. For computational efficiency the
square of the distance $r^2 = |\vec{x} - \vec{t}|^2$ is uniformly 
used as argument for $h$. Also, an additional argument $p$ has been
defined which represents the bias of the hidden units. The vectors
$\vec{x}$ and $\vec{t}$ result from the activation and weights of
links leading to the corresponding unit. The following radial basis
functions have been implemented:

\begin{enumerate}
\item{\tt Act\_RBF\_Gaussian} --- the Gaussian function
\index{Radial Basis Functions!Activation Function!Act\_RBF\_Gaussian}
\begin{eqnarray*}
h(r^2,p) = h(q,p) = e^{-pq} \quad\mbox{where}\quad q = |\vec{x} -
\vec{t}\, |^2
\end{eqnarray*}

\item{\tt Act\_RBF\_MultiQuadratic} --- the multiquadratic function
\index{Radial Basis Functions!Activation Function!Act\_RBF\_MultiQuadratic}
\begin{eqnarray*}
h(r^2,p) = h(q,p) = \sqrt{p + q} \quad\mbox{where}\quad q = |\vec{x} -
\vec{t}\, |^2
\end{eqnarray*}

\item{\tt Act\_RBF\_ThinPlateSpline} -- the {\sl thin plate splines} function
\index{Radial Basis Functions!Activation Function!Act\_RBF\_ThinPlateSpline}
\begin{eqnarray*}
h(r^2,p) = h(q,p) & = & p^2 q \ln(p \sqrt{q}) \quad\mbox{where}\quad q =
|\vec{x} - \vec{t}\, |^2 \\
& = & (pr)^2 \ln(pr) \quad\mbox{where}\quad r = |\vec{x} - \vec{t}\, |
\end{eqnarray*}

\end{enumerate}

During the construction of three layered neural networks based on
radial basis functions, it is important to use the three
activation functions mentioned above only for neurons inside the
hidden layer. There is also only one hidden layer allowed.

%\clearpage 

For the output layer two other activation functions are to be used:

\begin{enumerate}
\item{\tt Act\_IdentityPlusBias}

\item{\tt Act\_Logistic}
\end{enumerate}

\index{Radial Basis Functions!Activation Function!Act\_IdentityPlusBias}
{\tt Act\_IdentityPlusBias} activates the corresponding unit with the
weighted sum of all incoming activations and adds the
bias of the unit. {\tt Act\_Logistic} applies the sigmoid logistic
\index{Radial Basis Functions!Activation Function!Act\_Logistic}
function to the weighted sum which is computed like in {\tt
Act\_\-Identity\-Plus\-Bias}. In general, it is necessary to use an
activation function which pays attention to the bias of the unit.

The last two activation functions converge towards infinity, the first
converges towards zero.  However, all three functions are useful as
base functions. The mathematical preconditions for their use are
fulfilled by all three functions and their use is backed by practical
experience.  All three functions have been implemented as base
functions into SNNS.

The most frequently used base function is the Gaussian function. For
large distances $r$, the Gaussian function becomes almost $0$.
Therefore, the behavior of the net is easy to predict if the input
patterns differ strongly from all teaching patterns. Another advantage
of the Gaussian function is, that the network is able to produce
useful results without the use of shortcut connections between input
and output layer.

\subsubsection{Initialization Functions}
\label{RBF}
The goal in initializing a radial basis function  network is the optimal
computation of link weights between hidden and output layer. Here the
problem arises that the centers $\vec{t_j}$ (i.e.\ link weights
between input and hidden layer) as well as the parameter $p$ (i.e.\
the bias of the hidden units) must be set properly.  Therefore,
three different initialization procedures have been implemented which
perform different tasks:

\begin{enumerate}
\item {\tt RBF\_Weights}: This procedure first selects evenly
distributed centers $\vec{t_j}$ from the loaded training patterns and
assigns them to the links between input and hidden layer. Subsequently
the bias of all neurons (parameter $p$) inside the hidden layer is set
to a value determined by the user and finally the links between hidden
and output layer are computed.

\item {\tt RBF\_Weights\_Redo}: In contrast to the preceding procedure
only the links between hidden and output layer are computed. All other
links and bias remain unchanged.

\item {\tt RBF\_Weights\_Kohonen}: Using the self--organizing method
of Kohonen feature maps, appropriate centers are generated on base of
the teaching patterns. The computed centers are copied into the
corresponding links. No other links and bias are changed.

\end{enumerate}

It is necessary that valid patterns are loaded into SNNS to use the
initialization. If no patterns are present upon starting any of the
three procedures an alert box will occur showing the error. A detailed
description of the procedures and the parameters used is given in the
following paragraphs.

\paragraph*{RBF\_Weights}
\index{Radial Basis Functions!Initialization Function!RBF\_Weights}

Of the named three procedures {\tt RBF\_Weights} is the most
comprehensive one.  Here all necessary initialization tasks (setting
link weights and bias) for a fully connected three layer feedforward
network (without shortcut connections) can be performed in one single
step.  Hence, the choice of centers (i.e. the link weights between
input and hidden layer) is rather simple: The centers are evenly
selected from the loaded teaching patterns and assigned to the links
of the hidden neurons. The selection process assigns the first
teaching pattern to the first hidden unit, and the last pattern to the
last hidden unit. The remaining hidden units receive centers which are
evenly picked from the set of teaching patterns. If, for example, 13
teaching patterns are loaded and the hidden layer consists of 5
neurons, then the patterns with numbers 1, 4, 7, 10 and 13 are
selected as centers.

Before a selected teaching pattern is distributed among the
corresponding link weights it can be modified slightly with a random
number.  For this purpose, an initialization parameter ({\sl
deviation}, parameter 5) is set, which determines
the maximum percentage of deviation allowed to occur randomly. To
calculate the deviation, an inverse tangent function is used to
approximate a normal distribution so that small deviations are more
probable than large deviations.  Setting the parameter {\sl deviation}
to 1.0 results in a maximum deviation of 100\%. The centers are copied
unchanged into the link weights if the deviation is set to 0.

A small modification of the centers is recommended for the following
reasons: First, the number of hidden units may exceed the number of
teaching patterns. In this case it is necessary to break the symmetry
which would result without modification. This symmetry would render
the calculation of the Moore Penrose inverse matrix impossible. The
second reason is that there may be a few anomalous patterns inside the
set of teaching patterns.  These patterns would cause bad
initialization results if they accidentally were selected as a center.
By adding a small amount of noise, the negative effect caused by
anomalous patterns can be lowered. However, if an exact interpolation
is to be performed no modification of centers may be allowed.

The next initialization step is to set the free parameter $p$ of the
base function $h$, i.e. the bias of the hidden neurons. In order to
do this, the initialization parameter {\sl bias (p)} is directly
copied into the bias of all hidden neurons. The setting of the bias is
highly related to the base function $h$ used and to the properties of
the teaching patterns. When the Gaussian function is used, it is
recommended to choose the value of the bias so that 5--10\% of all
hidden neurons are activated during propagation of every single teaching
pattern. If the bias is chosen too small, almost all hidden neurons are
uniformly activated during propagation. If the bias is chosen too large,
only that hidden neuron is activated whose center vector corresponds
to the currently applied teaching pattern.

Now the expensive initialization of the links between hidden and
output layer is actually performed. In order to do this, the following
formula which was already presented above is applied:

\[
\vec{c} = ( G^T \cdot G + \lambda G_\Box)^{-1} \cdot G^T \cdot \vec{y}
\]

The initialization parameter 3 ({\sl smoothness}) represents the value
of $\lambda$ in this formula. The matrices have been extended to allow
an automatic computation of an additional constant value.  If there is
more than one neuron inside the output layer, the following set of
functions results:

\[f_j(\vec{x}) = \sum_{i=1}^K c_{i,j} h_i(\vec{x}) + b_j\] 

The bias of the output neuron(s) is directly set to the calculated value
of $b$ ($b_j$). Therefore, it is necessary to choose an
activation function for the output neurons that uses the bias of
the neurons. In the current version of SNNS, the functions {\tt
Act\_Logistic} and {\tt Act\_IdentityPlusBias} implement this feature. 

The activation functions of the output units lead to the remaining two
initialization parameters. The initialization procedure assumes a
linear activation of the output units. The link weights are calculated
so that the weighted sum of the hidden neurons equals the teaching
output. However, if a sigmoid activation function is used, which is
recommended for pattern recognition tasks, the activation function has
to be considered during initialization.  Ideally, the supposed input
for the activation function should be computed with the inverse
activation function depending on the corresponding teaching output.
This input value would be associated with the vector $\vec{y}$ during
the calculation of weights.  Unfortunately, the inverse activation
function is unknown in the general case.

The first and second initialization parameters ({\sl 0\_scale}) and
({\sl 1\_scale}) are a remedy for this dilemma. They define the two
control points of a piecewise linear function which approximates the
activation function.  {\sl 0\_scale} and {\sl 1\_ scale} give the net
inputs of the output units which produce the teaching outputs $0$ and
$1$. If, for example, the linear activation function {\tt
  Act\_IdentityPlusBias} is used, the values 0 and 1 have to be used.
When using the logistic activation function {\tt Act\_Logistic}, the
values -4 and 4 are recommended.  If the bias is set to 0, these
values lead to a final activation of $0.018$ (resp. $0.982$). These
are comparatively good approximations of the desired teaching outputs
0 and 1. The implementation interpolates linearly between the set
values of {\sl 0\_scale} and {\sl 1\_scale}. Thus, also teaching
values which differ from $0$ and $1$ are mapped to corresponding input
values.

\begin{figure}[htbp]
\begin{center}
  \begin{minipage}{\textwidth}
     \epsfbox{xgui_figs/log_bild.ps}
  \end{minipage}
\caption{Relation between teaching output, input value and logistic activation}
\label{i_skalierung}
\end{center}
\end{figure}


Figure~\ref{i_skalierung} shows the activation of an output unit under
use of the logistic activation function. The scale has been chosen in
such a way, that the teaching outputs $0$ and $1$ are mapped to the input
values $-2$ and $2$.

The optimal values used for {\sl 0\_scale} and {\sl 1\_scale} can not
be given in general. With the logistic activation function large
scaling values lead to good initialization results, but interfere with
the subsequent training, since the logistic function is used mainly in
its very flat parts. On the other hand, small scaling values lead
to bad initialization results, but produce good preconditions for
additional training.

\paragraph*{RBF\_Weights\_Kohonen}
\index{Radial Basis Functions!Initialization Function!
RBF\_Weights\_Kohonen}

One disadvantage of the above initialization procedure is the very
simple selection of center vectors from the set of teaching patterns.
It would be favorable if the center vectors would homogeneously cover
the space of teaching patterns. {\tt RBF\_Weights\_Kohonen} allows a
self--organizing training of center vectors. Here, just as the name of
the procedure already tells, the self--organizing maps of Kohonen are
used (see \cite{Wasser89}). The simplest version of Kohonen's maps has
been implemented. It works as follows:

One precondition for the use of Kohonen maps is that the teaching
patterns have to be normalized. This means, that they represent
vectors with length 1. $K$ patterns have to be selected from the set
of $n$ teaching patterns acting as starting values for the center
vectors.  Now the scalar product between one teaching pattern and each
center vector is computed. If the vectors are normalized to length 1,
the scalar product gives a measure for the distance between the two
multiplied vectors. Now the center vector is determined whose distance
to the current teaching pattern is minimal, i.e. whose scalar product
is the largest one. This center vector is moved a little bit in the
direction of the current teaching pattern:

\begin{eqnarray*}
\vec{z}_{\mbox{new}} = \vec{z}_{\mbox{old}} + \alpha (\vec{l} -
\vec{z}_{\mbox{old}})
\end{eqnarray*}

This procedure is repeated for all teaching patterns several times. As
a result, the center vectors adapt the statistical properties of the
set of teaching patterns.

The resp. meanings of the three initialization parameters are:

\begin{enumerate}

\item{\sl learn cycles}: determines the number of iterations of the
Kohonen training for all teaching patterns. If 0 epochs are specified
only the center vectors are set, but no training is performed.

\item{\sl learning rate} $\alpha$: It should be picked between 0 and
1. A learning rate of 0 leaves the center vectors unchanged. Using a
learning rate of 1 replaces the selected center vector by the current
teaching pattern.

\item{\sl shuffle}: Determines the selection of initial center vectors
at the beginning of the procedure. A value of 0 leads to the even
selection already described for {\tt RBF\_Weights}. Any value other
than 0 causes a random selection of center vectors from the set of
teaching patterns.
\end{enumerate}

Note, that the described initialization procedure initializes only the
center vectors (i.e.~the link weights between input and hidden layer).
The bias values of the neurons have to be set manually using the
graphical user interface. To perform the final initialization of
missing link weights, another initialization procedure has been
implemented.

\paragraph*{RBF\_Weights\_Redo}
\index{Radial Basis Functions!Initialization Function!
RBF\_Weights\_Redo}

This initialization procedure influences only the link weights between
hidden and output layer. It initializes the network as well as
possible by taking the bias and the center vectors of the hidden
neurons as a starting point. The center vectors can be set
by the previously described initialization procedure. Another
possibility is to create the center vectors by an external
procedure, convert these center vectors into a SNNS pattern file
and copy the patterns into the corresponding link weights by using
the previously described initialization procedure. When doing
this, Kohonen training must not be performed of course.

The effect of the procedure {\tt RBF\_Weights\_Redo} differs from 
{\tt RBF\_Weights} only in the way that the center vectors and
the bias remain unchanged. As expected, the last two initialization
parameters are omitted. The meaning and effect of the remaining three
parameters is identical with the ones described in {\tt RBF\_Weights}.


\subsubsection{Learning Functions}
\index{Radial Basis Functions!Learning Function}

Because of the special activation functions used for radial basis
functions, a special learning function is needed. It is impossible to
train networks which use the activation functions {\tt Act\_}\-{\tt
RBF\_$\ldots$} with backpropagation. The learning function for radial
basis functions implemented here can only be applied if the neurons
which use the special activation functions are forming the hidden
layer of a three layer feedforward network. Also the neurons of the
output layer have to pay attention to their bias for activation.

The name of the special learning function is {\tt
RadialBasisLearning}. The required parameters are:

\begin{enumerate}
\item{\sl $\eta_1$ (centers)}: the learning rate used for the
modification $\Delta \vec{t_j}$ of center vectors according to the
formula $ \Delta \vec{t_j} = - \eta_1 \frac{\partial E}{\partial
\vec{t_j}} $.

\item{\sl $\eta_2$ (bias p)}: learning rate used for the modification
of the parameters $p$ of the base function. $p$ is stored as bias of
the hidden units and is trained by the following formula $\Delta p_j =
- \eta_2 \frac{\partial E}{\partial p_j}$.

\item{\sl$\eta_3$ (weights)}: learning rate which influences the
training of all link weights that are leading to the output layer as
well as the bias of all output neurons.

\[
\Delta c_{j,k} = - \eta_3 \frac{\partial E}{\partial c_{j,k}} \quad ,
\quad \Delta d_{i,k} = - \eta_3 \frac{\partial E}{\partial d_{i,k}}
\quad , \quad \Delta b_k = - \eta_3 \frac{\partial E}{\partial b_{k}}
\]

\item{\sl delta max.}: To prevent an overtraining of the network the
maximally tolerated error in an output unit can be defined. If the
actual error is smaller than {\sl delta max.} the corresponding
weights are not changed. Common values range from 0 to $0.3$.

\item{\sl momentum}: momentum term during training, after the formula
$\Delta g_{t+1} = - \eta \frac{\partial E}{\partial g} + \mu \Delta
g_{t}$. The momentum--term is usually chosen between $0.8$ and $0.9$.

\end{enumerate}

The learning rates $\eta_1$ to $\eta_3$ have to be selected very
carefully.  If the values are chosen too large (like the size of
values for backpropagation) the modification of weights will be too
extensive and the learning function will become unstable. Tests
showed, that the learning procedure becomes more stable if only one of
the three learning rates is set to a value bigger than 0. Most
critical is the parameter {\sl bias (p)}, because the base functions
are fundamentally changed by this parameter.

\index{Radial Basis Functions!Learning!Batch Mode}
Tests also showed that the learning function working in batch mode is
much more stable than in online mode. Batch mode means that all
changes become active not before all learning patterns have been
presented once. This is also the training mode which is recommended in
the literature about radial basis functions. The opposite of batch
\index{Radial Basis Functions!Learning!Online Mode}
mode is known as online mode, where the weights are changed after the
presentation of every single teaching pattern. Which mode is to be
used can be defined during compilation of SNNS. The online mode is
activated by defining the C macro {\tt RBF\_INCR\_LEARNING} during
compilation of the simulator kernel, while batch mode is the default.

\subsection{Building a Radial Basis Function Application}
\index{Example!Radial Basis Functions}
\index{Radial Basis Functions!Example}
As a first step, a three--layer feedforward network must be
constructed with full connectivity between input and hidden layer and
between hidden and output layer. Either the graphical editor or the
tool {\tt BIGNET} (both built into SNNS) can be used for this purpose.

The output function of all neurons is set to {\tt Out\_}\-{\tt
Iden\-tity}.  The activation function of all hidden layer neurons is
set to one of the three special activation functions {\tt
Act\_RBF\_$\ldots$} (preferably to {\tt Act\_RBF\_Gaussian}). For the
activation of the output units, a function is needed which takes the
bias into consideration.  These functions are {\tt Act\_Logistic} and
{\tt Act\_Identity}\-{\tt Plus}\-{\tt Bias}.

The next step consists of the creation of teaching patterns. They can
be generated manually using the graphical editor, or automatically
from external data sets by using an appropriate conversion program. If
the initialization procedure {\tt RBF\_Weights\_Kohonen} is going to
be used, the center vectors should be normalized to length 1, or to
equal length.

It is necessary to select an appropriate bias for the hidden units
before the initialization is continued. Therefore, the link weights
between input and hidden layer are set first, using the procedure {\tt
RBF\_Weights\_Kohonen} so that the center vectors which are
represented by the link weights form a subset of the available teaching
patterns. The necessary initialization parameters are: {\sl learn
cycles} $=0$, {\sl learning rate} $=0.0$, {\sl shuffle} $=0.0$.
Thereby teaching patterns are used as center vectors without
modification.

To set the bias, the activation of the hidden units is checked for
different teaching patterns by using the button \mbox{TEST} of the
SNNS control panel. When doing this, the bias of the hidden neurons
have to be adjusted so that the activations of the hidden units are as
diverse as possible. Using the Gaussian function as base function, all
hidden units are uniformly highly activated, if the bias is chosen too
small (the case bias $=0$ leads to an activation of 1 of all hidden
neurons). If the bias is chosen too large, only the unit is activated
whose link weights correspond to the current teaching pattern. A
useful procedure to find the right bias is to first set the bias to 1,
and then to change it uniformly depending on the behavior of the
network. One must take care, however, that the bias does not become
negative, since some implemented base functions require the bias to be
positive. The optimal choice of the bias depends on the dimension of
the input layer and the similarity among the teaching patterns.

After a suitable bias for the hidden units has been determined, the
initialization procedure {\tt RBF\_Weights} can be started. Depending
on the selected activation function for the output layer, the two {\sl
scale} pa\-ra\-meters have to be set (see
page~\pageref{i_skalierung}).  When {\tt Act\_\-Identity\-Plus\-Bias}
is used, the two values 0 and 1 should be chosen. For the logistic
activation function {\tt Act\_\-Logistic} the values -4 and 4 are
recommended (also see figure~\ref{i_skalierung}). The parameters {\sl
smoothness} and {\sl deviation} should be set to 0 first. The {\sl
bias} is set to the previously determined value. Depending on the
number of teaching patterns and the number of hidden neurons, the
initialization procedure may take rather long to execute. Therefore,
some processing comments are printed on the terminal during
initialization.

After the initialization has finished, the result may be checked by
using the \fbox{TEST} button. However, the exact network error can
only be determined by the teaching function. Therefore, the learning
function {\tt Radial\-Basis\-Learning} has to be selected first. All
learning parameters are set to 0 and the number of learning cycles
(CYCLES) is set to 1. After pressing the button \fbox{ALL}, the
learning function is started. Since the learning parameters are set to
0, no changes inside the network will occur. After the
presentation of all available teaching patterns, the actual error is
printed to the terminal. As usual, the error is defined as the sum of
squared errors of all output units (see
formula~\ref{a_fehler_formel}). Under certain conditions it can be
possible that the error becomes very large. This is mostly due to
numerical problems. A poorly selected bias, for example, has shown to
be a difficult starting point for the initialization. Also, if the
number of teaching patterns is less than or equal to the number of hidden
units a problem arises. In this case the number of unknown
weights plus unknown bias values of output units exceeds the number of
teaching patterns, i.e.\ there are more unknown parameters to be
calculated than equations available. One or more neurons less inside
the hidden layer then reduces the error considerably.

After the first initialization it is recommended to save the current
network to test the possibilities of the learning function.  It has
turned out that the learning function becomes quickly unstable if too
large learning rates are used. It is recommended to first set only one
of the three learning rates ({\sl centers, bias (p), weights}) to a
value larger than 0 and to check the sensitivity of the learning
function on this single learning rate. The use of the parameter {\sl
bias (p)} is exceptionally critical because it causes serious changes
of the base function. If the bias of any hidden neuron is getting
negative during learning, an appropriate message is printed to the
terminal. In that case, a continuing meaningful training is
impossible and the network should be reinitialized.

Immediately after initialization it is often useful to train only
the link weights between hidden and output layer. Thereby the
numerical inaccuracies which appeared during initialization are
corrected. However, an optimized total result can only be achieved if
also the center vectors are trained, since they might have been
selected disadvantageously.

The initialization procedure used for direct link weight calculation is
unable to calculate the weights between input and output layer.
If such links are present, the following procedure is recommended:
Even before setting the center vectors by using {\tt
RBF\_Weights\_Kohonen}, and before searching an appropriate bias, all
weights should be set to random values between $-0.1$ and $0.1$
by using the initialization procedure {\tt Randomize\_Weights}.
Thereby, all links between input and output layer are
preinitialized.  Later on, after executing the procedure {\tt
RBF\_Weights}, the error of the network will still be relatively large,
because the above mentioned links have not been considered. Now it is
easy to train these weights by only using the teaching parameter {\sl
weights} during learning.



\section{Dynamic Decay Adjustment for RBFs (RBF--DDA)}

\subsection{The Dynamic Decay Adjustment Algorithm}

The Dynamic Decay Adjustment (DDA--)Algorithm is an extension of the
RCE-Algorithm (see~\cite{Huda92,ReCE82}) and offers easy and
constructive training for Radial Basis Function Networks. RBFs
trained with the DDA-Algorithm often achieve classification accuracy
comparable to Multi Layer Perceptrons (MLPs)\footnote{ As usual the
  term MLP refers to a multilayer feedforward network using the scalar
  product as a propagation rule and sigmoids as transfer functions.  }
but training is significantly faster (\cite{BeDi95}).

An RBF trained with the DDA-Algorithm (RBF-DDA) is similar 
in structure to the common feedforward MLP with one hidden layer
and without shortcut connections:
\begin{itemize}
  \item The number of units in the {\bf input layer} represents
        the dimensionality of the input space.
  \item The {\bf hidden layer} contains the RBF units.
        Units are added in this layer during training.
        The input layer is fully connected to the hidden layer.
  \item Each unit in the {\bf output layer} represents one 
        possible class, resulting in an 1-of-n or binary coding.
        For classification a winner-takes-all approach is used,
        i.e. the output with the highest activation determines
        the class. Each hidden unit is connected to exactly one output unit.
\end{itemize}

The main differences to an MLP are the activation function and
propagation rule of the hidden layer: Instead of using a sigmoid or
another nonlinear squashing function, RBFs use localized functions,
radial Gaussians, as an activation function. In addition, a
computation of the Euclidian distance to an individual reference
vector replaces the scalar product used in MLPs:
\[
    R_i(\vec{x}) = exp(-\frac{||\vec{x}-\vec{r}_i||^2}{\sigma_i^2})
\]
If the network receives vector $\vec{x}$ as an input, $R_i$ indicates
the activation of one RBF unit with reference vector $\vec{r}_i$ and
standard deviation $\sigma_i$.

The output layer computes the output for each class as follows:
\[
    f(\vec{x})=\sum_{i=1}^{m}A_i*R_i(\vec{x}) 
\]
with $m$ indicating the number of RBFs belonging to the corresponding
class and $A_i$ being the weight for each RBF.

An example of a full RBF-DDA is shown in figure~\ref{rbfdda-net}.
Note that there do not exist any shortcut connections between input
and output units in an RBF-DDA.

\begin{figure}[htbp]
\begin{center}
  \begin{minipage}{\textwidth}
    \screendump{0.6}{nn_models/rbf-net.ps}
  \end{minipage}
  \caption{The structure of a Radial Basis Function Network.}
  \label{rbfdda-net}
\end{center}
\end{figure}


In this illustration the weight vector that connects all input units
to one hidden unit represents the centre of the Gaussian. The
Euclidian distance of the input vector to this reference vector (or
{\it prototype}) is used as an input to the Gaussian which leads to a
local response; if the input vector is {\it close} to the prototype,
the unit will have a high activation. In contrast the activation will
be close to zero for larger distances.  Each output unit simply
computes a weighted sum of all activations of the RBF units belonging
to the corresponding class.

The DDA-Algorithm introduces the idea of distinguishing between {\it
  matching} and {\it conflicting} neighbors in an {\it area of
  conflict}. Two thresholds $\theta^{+}$ and $\theta^{-}$ are
introduced as illustrated in figure~\ref{one-dda-rbf}.

\begin{figure}[htbp]
\begin{center}
  \begin{minipage}{\textwidth}
    \screendump{0.6}{nn_models/dda_unit.ps}
  \end{minipage}
  \caption{One RBF unit as used by the DDA-Algorithm. Two {\it thresholds}     
           are used to define an {\it area of conflict} where no        
           other prototype of a conflicting class is allowed to exist.
           In addition, each training pattern has to be in the inner
           circle of at least one prototype of the correct class.}
  \label{one-dda-rbf}
\end{center}
\end{figure}

Normally, $\theta^{+}$ is set to be greater than $\theta^{-}$ which
leads to a {\it area of conflict} where neither matching nor
conflicting training patterns are allowed to lie\footnote{The only
  exception to this rule is the case where a pattern of the same class
  lies in the area of conflict but is covered by another RBF (of the
  correct class) with a sufficiently high activation.}.  Using these
thresholds, the algorithm constructs the network dynamically and
adjusts the radii individually.

In short the main properties of the DDA-Algorithm are:
\begin{itemize}
\item {\bf constructive training}: new RBF nodes are added whenever necessary.
      The network is built from scratch, the number of required
      hidden units is determined during training. Individual radii 
      are adjusted dynamically during training.
\item {\bf fast training}: usually about five epochs are needed to complete
      training, due to the constructive nature of the algorithm. 
      End of training is clearly indicated.     
\item {\bf guaranteed convergence}: the algorithm can be proven to
      terminate.
\item {\bf two uncritical parameters}: only the two parameters $\theta^{+}$
      and $\theta^{-}$ have to
      be adjusted manually. Fortunately the values of these two
      thresholds are not critical to determine. For all tasks that have
      been used so far, $\theta^{+}=0.4$ and $\theta^{-}=0.2$ was
      a good choice.
\item {\bf guaranteed properties} of the network: it can be shown that
      after training has terminated, the network holds several conditions for
      all training patterns: wrong classifications are below a certain
      threshold ($\theta^{-}$) and correct classifications are above 
      another threshold ($\theta^{+}$).
\end{itemize}

The DDA-Algorithm is based on two steps. During training, whenever a
pattern is misclassified, either a new RBF unit with an initial weight
= 1 is introduced (called {\it commit}) or the weight of an existing
RBF (which covers the new pattern) is incremented. In both cases the
radii of conflicting RBFs (RBFs belonging to the wrong class) are
reduced (called {\it shrink}).  This guarantees that each of the
patterns in the training data is covered by an RBF of the correct
class and none of the RBFs of a conflicting class has an inappropriate
response.

Two parameters are introduced at this stage, a {\it positive threshold}
$\theta^{+}$ and a {\it negative threshold} $\theta^{-}$. To commit
a new prototype, none of the existing RBFs of the correct class has
an activation above $\theta^{+}$ and during shrinking no RBF of
a conflicting class is allowed to have an activation above $\theta^{-}$.
Figure~\ref{dda-exp} shows an example that illustrates the first
few training steps of the DDA-Algorithm.


\begin{figure}[htbp]
\begin{center}
  \begin{minipage}{3.6cm}
    \screendump{0.4}{nn_models/dda_step1.ps}
  \end{minipage}
  \hfill
  \begin{minipage}{3.6cm}
    \screendump{0.4}{nn_models/dda_step2.ps}
  \end{minipage}
  \vspace{0.1cm}
  \centerline{(1)\hspace{3.7cm}(2)}
  \vspace{0.5cm}
  \begin{minipage}{3.6cm}
    \screendump{0.4}{nn_models/dda_step3.ps}
  \end{minipage}
  \hfill
  \begin{minipage}{3.6cm}
    \screendump{0.4}{nn_models/dda_step4.ps}
  \end{minipage}
  \vspace{0.1cm}
  \centerline{(3)\hspace{3.7cm}(4)}
  \vspace{0.1cm}
  \caption{An example of the DDA-Algorithm: (1) a pattern of class $A$
    is encountered and a new RBF is created; (2) a training pattern of
    class $B$ leads to a new prototype for class $B$ and shrinks the
    radius of the existing RBF of class $A$; (3) another pattern of
    class $B$ is classified correctly and shrinks again the prototype
    of class $A$; (4) a new pattern of class $A$ introduces another
    prototype of that class.}
  \label{dda-exp}
\end{center}
\end{figure}

After training is finished, two conditions are true for all input--output
pairs\footnote{In this case the term ``input--class pair'' would
  be more justified, since the DDA--Algorithm trains the network to
  classify rather than approximate an input--output mapping.}
$(\vec{x}, c)$ of the training data:
\begin{itemize}
\item at least one prototype of the correct class $c$ has an activation value
      greater or equal to $\theta^{+}$:
  \[
    \exists i : R_i^c(\vec{x})\geq \theta^{+}
  \]
\item all prototypes of conflicting classes have activations less or equal to
      $\theta^{-}$ ($m_k$ indicates the number of prototypes belonging
      to class $k$):
  \[
    \forall k\neq c, 1\leq j\leq m_k: R_j^k(\vec{x})\leq \theta^{-}
  \]
\end{itemize}

For all experiments conducted so far, the choice of $\theta^{+}$=0.4
and $\theta^{-}$=0.2 led to satisfactory results. In theory, those
parameters should be dependent on the dimensionality of the feature
space but in practice the values of the two thresholds seem to be
uncritical.  Much more important is that the input data is normalized.
Due to the radial nature of RBFs each attribute should be distributed
over an equivalent range. Usually normalization into [0,1] is
sufficient.


\subsection{Using RBF--DDA in SNNS}

The implementation of the DDA-Algorithm always uses the Gaussian
activation function {\tt Act\_RBF\_Gaussian} in the hidden layer.  All
other activation and output functions are set to {\tt Act\_Identity}
and {\tt Out\_Identity}, respectively.

The {\it Learning function} has to be set to {\tt RBF-DDA}. 
No {\it Initialization} or {\it Update} functions are needed.

The algorithm takes three arguments that are set in the first three
fields of the {\tt LEARN} row in the {\it control panel}. These are
$\theta^{+}$, $\theta^{-}$ ($0 < \theta^{-}\leq\theta^{+} < 1$) and
the maximum number of RBF units to be diplayed in one row.  This last
item allows the user to control the appearance of the network on the
screen and has no influence on the performance.  Specifying 0.0 leads
to the default values $\theta^{+}=0.4$, $\theta^{-}=0.2$ and to a
maximum number of 20 RBF units displayed in a row.

Training of an RBF starts with either:
\begin {itemize}
\item   an {\bf empty} network, i.e.~a network consisting only
        of input and output units. No connections between input and
        output units are required, hidden units will be added during
        training. This can easily be 
        generated with the tool {\tt BIGNET} (choice {\tt FEED FORWARD})
\item   a {\bf pretrained} network already containing RBF units generated
        in an earlier run of {\tt RBF-DDA} (all networks not complying with 
        the specification of an RBF-DDA will be rejected).
\end{itemize}

After having loaded a training pattern set, a {\it learning-epoch} can
be started by pressing the {\tt ALL} button in the {\it control panel}.
At the beginning of each epoch, the weights between the hidden and the
output layer are automatically set to zero.  Note that the resulting
RBF and the number of required learning epochs can vary slightly
depending on the order of the training patterns.  If you train using a
single pattern (by pressing the {\tt SINGLE} button) keep in mind that
every training step increments the weight between the RBF unit of the
correct class covering that pattern and its corresponding output unit.
The end of the training is reached when the network structure does not
change any more and the Mean Square Error (MSE) stays constant from
one epoch to another.

The first desired value in an output pattern that is greater than 0.0
will be assumed to represent the class this pattern belongs to; only
one output may be greater than 0.0.  If there is no such output,
training is still executed, but no new prototype for this pattern is
commited. All existing prototypes are shrunk to avoid coverage of this
pattern, however.  This can be an easy way to define an
``error''--class without trying to model the class itself.



\section{ART Models in SNNS}
\label{art models in snns}
\index{ART}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Definition einiger simpler Text-Makros

\newcommand{\fn}[0]{F$_0$}
\newcommand{\fe}[0]{F$_1$}
\newcommand{\fz}[0]{F$_2$}
\newcommand{\fea}[0]{F$_1^a$}
\newcommand{\feb}[0]{F$_1^b$}
\newcommand{\fza}[0]{F$_2^a$}
\newcommand{\fzb}[0]{F$_2^b$}
\newcommand{\fab}[0]{F$^{ab}$}

\newcommand{\arta}[0]{ART$^a$}
\newcommand{\artb}[0]{ART$^b$}

\newcommand{\rhog}[0]{$\rho$}
\newcommand{\rhoa}[0]{$\rho^a$}
\newcommand{\rhoastart}[0]{$\overline{\rho^a}$}
\newcommand{\rhob}[0]{$\rho^b$}

\newcommand{\Na}[0]{$N^a$}
\newcommand{\Nb}[0]{$N^b$}
\newcommand{\Ma}[0]{$M^a$}
\newcommand{\Mb}[0]{$M^b$}

\newcommand{\inp}[1]{{\bf inp}$_{#1}$}
\newcommand{\cmp}[1]{{\bf cmp}$_{#1}$}
\newcommand{\rec}[1]{{\bf rec}$_{#1}$}
\newcommand{\del}[1]{{\bf del}$_{#1}$}
\newcommand{\rst}[1]{{\bf rst}$_{#1}$}
\newcommand{\inpa}[1]{{\bf inp}$_{#1}^a$}
\newcommand{\inpb}[1]{{\bf inp}$_{#1}^b$}
\newcommand{\cmpa}[1]{{\bf cmp}$_{#1}^a$}
\newcommand{\cmpb}[1]{{\bf cmp}$_{#1}^b$}
\newcommand{\reca}[1]{{\bf rec}$_{#1}^a$}
\newcommand{\recb}[1]{{\bf rec}$_{#1}^b$}
\newcommand{\dela}[1]{{\bf del}$_{#1}^a$}
\newcommand{\delb}[1]{{\bf del}$_{#1}^b$}
\newcommand{\rsta}[1]{{\bf rst}$_{#1}^a$}
\newcommand{\rstb}[1]{{\bf rst}$_{#1}^b$}

\newcommand{\map}[1]{{\bf map}$_{#1}$}

\newcommand{\da}[1]{{\bf d}$_{#1}^a$}
\newcommand{\db}[1]{{\bf d}$_{#1}^b$}
\newcommand{\de}[0]{{\bf d}$_1$}


\newcommand{\geu}[0]{{\bf g}$_1$}
\newcommand{\gzu}[0]{{\bf g}$_2$}

\newcommand{\gea}[0]{{\bf g}$_1^a$}
\newcommand{\geb}[0]{{\bf g}$_1^b$}
\newcommand{\gza}[0]{{\bf g}$_2^a$}
\newcommand{\gzb}[0]{{\bf g}$_2^b$}
\newcommand{\ria}[0]{{\bf ri}$^a$}
\newcommand{\rib}[0]{{\bf ri}$^b$}
\newcommand{\rca}[0]{{\bf rc}$^a$}
\newcommand{\rcb}[0]{{\bf rc}$^b$}
\newcommand{\rga}[0]{{\bf rg}$^a$}
\newcommand{\rgb}[0]{{\bf rg}$^b$}
\newcommand{\cla}[0]{{\bf cl}$^a$}
\newcommand{\clb}[0]{{\bf cl}$^b$}
\newcommand{\nca}[0]{{\bf nc}$^a$}
\newcommand{\ncb}[0]{{\bf nc}$^b$}

\newcommand{\G}[0]{{\bf G}}
\newcommand{\rb}[0]{{\bf rb}}
\newcommand{\resm}[0]{{\bf rm}}
\newcommand{\rg}[0]{{\bf rg}}
\newcommand{\cl}[0]{{\bf cl}}
\newcommand{\nc}[0]{{\bf nc}}
\newcommand{\qu}[0]{{\bf qu}}
\newcommand{\drho}[0]{$\Delta \rho$}

\newcommand{\wk}[1]{{\bf w}$_{#1}$}
\newcommand{\xk}[1]{{\bf x}$_{#1}$}
\newcommand{\uk}[1]{{\bf u}$_{#1}$}
\newcommand{\vk}[1]{{\bf v}$_{#1}$}
\newcommand{\pk}[1]{{\bf p}$_{#1}$}
\newcommand{\qk}[1]{{\bf q}$_{#1}$}
\newcommand{\rk}[1]{{\bf r}$_{#1}$}

\newcommand{\actid}[0]{{\tt Act\_Identity}}
\newcommand{\actartzid}[0]{{\tt Act\_ART2\_Identity}}
\newcommand{\outid}[0]{{\tt Out\_Identity}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% FRACTION - Values
% =================
% Adjust values for figures and text on one page
\renewcommand{\topfraction}[0]{1.0}
\renewcommand{\bottomfraction}[0]{1.0}
\renewcommand{\textfraction}[0]{0.0}
\renewcommand{\floatpagefraction}[0]{1.0}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%% Math-Mini-Space
\newcommand{\mms}[0]{\mbox{\hspace*{1mm}}}

\newenvironment{ttscript}[1]{\begin{list}{}{\settowidth{\labelwidth}{\tt #1}
   \setlength{\leftmargin}{\labelwidth} \addtolength{\leftmargin}{\labelsep}
   \parsep0.5ex plus0.2ex minus0.2ex \itemsep 0.3ex
   \renewcommand{\makelabel}[1]{\tt ##1\hfill}}}{\end{list}}

\newenvironment{ttnpscript}[1]{\begin{list}{}{\settowidth{\labelwidth}{\tt #1}
   \setlength{\leftmargin}{\labelwidth} \addtolength{\leftmargin}{\labelsep}
   \parsep0ex plus0.2ex \itemsep 0ex
   \renewcommand{\makelabel}[1]{\tt ##1\hfill}}}{\end{list}}

\newenvironment{varscript}[2]{\begin{list}{}{\settowidth{\labelwidth}%
   {\begin{#1}#2\end{#1}}
   \setlength{\leftmargin}{\labelwidth} \addtolength{\leftmargin}{\labelsep}
   \parsep0.5ex plus0.2ex minus0.2ex \itemsep 0.3ex
   \renewcommand{\makelabel}[1]{\begin{#1}##1\end{#1}\hfill}}}{\end{list}}

\newenvironment{varnpscript}[2]{\begin{list}{}{\settowidth{\labelwidth}%
   {\begin{#1}#2\end{#1}}
   \setlength{\leftmargin}{\labelwidth} \addtolength{\leftmargin}{\labelsep}
   \parsep0ex plus0.2ex \itemsep 0ex
   \renewcommand{\makelabel}[1]{\begin{#1}##1\end{#1}\hfill}}}{\end{list}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


This section will describe the use of the three ART models ART1, ART2
and ARTMAP, as they are implemented in SNNS.  It will not give
detailed information on the \index{Adaptive Resonance Theory} Adaptive
Resonance Theory. You should already know the theory to be able to
understand this chapter. For the theory the following literature is
recommended:

\begin{varscript}{rm}{CG87b}
\item[\cite{CG87a}]  Original paper, describing ART1 theory.
\item[\cite{CG87b}]  Original paper, describing ART2 theory.
\item[\cite{CG91}]   Original paper, describing ARTMAP theory.
\item[\cite{Her92}]  Description of theory, implementation and application
                     of the ART models in SNNS (in German).
\end{varscript}

There will be one subsection for each of the three models and one subsection
describing the required topologies of the networks when using the ART
learning-, update- or initialization-functions. These topologies are
rather complex. For this reason the network creation tool {\bf BigNet}
has been extended.  It now offers an easy way to create ART1, ART2 and
ARTMAP networks according to your requirements.  For a detailed
explanation of the respective features of {\bf BigNet} see
chapter~\ref{Bignet}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{ART1}
\label{art1}
\index{ART1}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Structure of an ART1 Network}
\label{structure of an art1 network}
\index{ART1!structure}
\index{ART1!topology}

\begin{figure}
 \begin{center}
  \begin{minipage}{9cm}
    \screendump{0.7}{nn_models/art1ee.ps}
    \label{art1 structure}
  \end{minipage}
  \hfill
  \parbox{5cm}{
    \caption{\newline Structure of an ART1 network in SNNS. Thin
      arrows represent a connection from one unit to another. Fat
      arrows which go from a layer to a unit indicate that each unit
      of the layer is connected to the target unit. Similarly a fat
      arrow from a unit to a layer means that the source unit is
      connected to each of the units in the target layer. The two big
      arrows in the middle represent the full connection between
      comparison and recognition layer and the one between delay and
      comparison layer, respectively.}
    }
 \end{center}
\end{figure}

The topology of ART1 networks in SNNS has been chosen to to perform
most of the ART1 algorithm within the network itself. This means that
the mathematics is realized in the activation and output functions of
the units.  The idea was to keep the propagation and training
algorithm as simple as possible and to avoid procedural control
components.

In figure~\ref{art1 structure} the units and links
of ART1 networks in SNNS are displayed.


The \fn~or input layer (labeled {\bf inp} in figure~\ref{art1 structure})
is a set of $N$ input units. Each of them
has a corresponding unit in the \fe~or comparison layer
(labeled {\bf cmp}). The $M$ elements in the \fz~layer are split into
three levels. So each \fz~element consists of three units. One
recognition ({\bf rec}) unit, one delay ({\bf del}) unit and
one local reset ({\bf rst}) unit.
These three parts are necessary for different reasons. The recognition
units are known from the theory. The delay units are needed
to synchronize the network correctly\footnote{This is only important for
the chosen realization of the ART1 learning algorithm in SNNS}.
Besides, the activated unit in the delay layer shows the winner of
\fz.
The job of the local reset units
is to block the actual winner of the recognition layer in case of a reset.

Finally, there are several special units. The \cl~unit gets
positive activation when the input pattern has been successfully
classified. The \nc~unit indicates an unclassifiable pattern,
when active. The gain units \geu~and \gzu~with their known functions and
at last the units {\bf ri} (reset input), {\bf rc} (reset comparison),
{\bf rg} (reset general) and \rhog (vigilance), which
realize the reset function.

For an exact definition of the required topology for ART1 networks in
SNNS see section~\ref{topology of art networks in snns}


\subsubsection{Using ART1 Networks in SNNS}
\label{ART1}
\label{using art1 networks in snns}
\index{ART1!usage}

To use an ART1 network in SNNS several functions have been 
implemented: one to initialize the network, one to train it and two
different update functions to propagate an input pattern through
the net.


\paragraph*{ART1 Initialization Function}
\index{ART1!initialization function}

First the ART1 initialization function {\tt ART1\_Weights} has to be
selected from the list of initialization functions.

{\tt ART1\_Weights} is responsible to set the initial values of the trainable
links in an ART1 network. These links are the ones
from \fe~to \fz~and the ones from \fz~to \fe~respectively.

The \fz~$\rightarrow$ \fe~links are all set to 1.0 as described
in~\cite{CG87a}. The weights of the links from \fe~to \fz~are
a little more difficult to explain. To assure that in an initialized
network the \fz~units will be used in their index order,
the weights from \fe~to \fz~must decrease with increasing index. Another
restriction is, that each link-weight has to be greater than $0$ and
smaller than $1/N$. Defining $\alpha_j$ as a link-weight from a
\fe~unit to the $j$\/th \fz~unitthis yields

\begin{equation}
   0 < \alpha_M < \alpha_{M-1} < \dots < \alpha_1 \leq \frac{1}{\beta+N}.
\label{eq f1 f2 weights 1}
\end{equation}

To get concrete values, we have to decrease the
fraction on the right side with increasing index $j$ and assign this
value to $\alpha_j$. For this reason we introduce the value
$\eta$ and we obtain

\begin{equation}
  \alpha_j \equiv \frac{1}{\beta + (1 + j \eta) N}.
\label{eq f1 f2 weights 2}
\end{equation}

$\eta$ is calculated out of a new parameter $\gamma$ and the
number of \fz~units $M$:

\begin{equation}
   \eta \equiv \frac{\gamma}{M}.
\label{eq f1 f2 weights 3}
\end{equation}

So we have two parameters for {\tt ART1\_Weights}: $\beta$ and
$\gamma$.  For both of them a value of 1.0 is useful for the
initialization.  The first parameter of the initialization function is
$\beta$, the second one is $\gamma$.  Having chosen $\beta$ and
$\gamma$ one must press the \fbox{INIT}-button to perform
initialization.

The parameter $\beta$ is stored in the bias field of the unit
structure to be accessible to the learning function when 
adjusting the weights.

One should always use {\tt ART1\_Weights} to initialize
ART1 networks. When using another SNNS initialization function the
behavior of the simulator during learning is not predictable, because not only
the trainable links will be initialized, but also the fixed weights
of the network.


\paragraph*{ART1 Learning Function}
\index{ART1!learning function}

To train an ART1 network select the learning function {\tt ART1}.
To start the training of an ART1 network, choose the vigilance
parameter $\rho$ (e.g.: 0.1) as first value in both {\tt LEARN} and
{\tt UPDATE} row of the control panel.  Parameter $\beta$, which is
also needed to adjust the trainable weights between \fe~and \fz, has
already been specified as initialization parameter. It is stored in
the bias field of the unit structure and read out by {\tt ART1} when
needed.


\paragraph*{ART1 Update Functions}
\index{ART1!update functions}

To propagate a new pattern through an ART1 network without adjusting
weights, i.e.~to classify a pattern, two different update functions
have been implemented:

\begin{itemize}
\item {\tt ART1\_Stable} \hspace{2cm} and
\item {\tt ART1\_Synchronous}.
\end{itemize}

Like the learning function, both of the update functions only take
the vigilance value $\rho$ as parameter. It has to be entered in
the control panel, the line below the parameters for the
learning function.
The difference between the
two update functions is the following:

{\tt ART1\_Stable} propagates a
pattern until the network is stable, i.e.~either the \cl~unit or
the \nc~unit is active. To use this update function, you can
use the \fbox{TEST}-button of the control panel. The next pattern
is copied to the input units and propagated completely through the
net, until a stable state is reached.

{\tt ART1\_Synchronous}, performs just one
propagation step with each call. To use this function you have
to press the \fbox{RESET}-button to reset the net to a defined
initial state, where each unit has its initial activation value.
Then copy a new pattern into the input layer, using the buttons
\fbox{$<$} and \fbox{$>$}. Now you can choose the desired number of
propagation steps that should be performed, when pressing the
\fbox{STEP}-button (default is 1). With this update function
it is very easy to observe how the ART1 learning algorithm
does its job.

So use {\tt ART1\_Synchronous},
to {\em trace} a pattern through a network, {\tt ART1\_Stable} to
propagate the pattern until a stable state is reached.



\subsection{ART2}
\label{art2}
\index{ART2}

\subsubsection{Structure of an ART2 Network}
\index{ART2!structure}
\index{ART2!topology}

The realization of ART2 differs from the one of ART1 in its basic idea.
In this case the network structure would have been too complex,
if mathematics had been implemented within the network to the same
degree as it has been done for ART1. So here more of the functionality
is in the control program.
In figure~\ref{art2 structure} you can see the topology of an ART2
network as it is implemented in SNNS.

\begin{figure}
 \begin{center}
  \begin{minipage}{9cm}
    \screendump{0.7}{nn_models/art2ee.ps}
    \label{art2 structure}
  \end{minipage}
  \hfill
  \parbox{5cm}{
    \caption{\newline Structure of an ART2 network in SNNS. Thin
      arrows represent a connection from one unit to another.  The two
      big arrows in the middle represent the full connectivity between
      comparison and recognition layer and the one between recognition
      and comparison layer, respectively. } 
    }
 \end{center}
\end{figure}

All the units are known from the ART2 theory, except the {\bf rst} units. They
have to do the same job for ART2 as for ART1 networks. They block the
actual winner in the recognition layer in case of reset.
Another difference between the ART2 model described in~\cite{CG87b} and
the realization in SNNS is, that originally the
units \uk{i} have been used to compute the error vector {\bf r}, while
this implementation takes the input units instead.

For an exact definition of the required topology for ART2 networks in
SNNS see section~\ref{topology of art networks in snns}


\subsubsection{Using ART2 Networks in SNNS}
\label{using art2 networks in snns}
\index{ART2!usage}
\label{ART2}
As for ART1 there are an initialization function, a learning function
and two update functions for ART2. To initialize, train or test an
ART2 network, these functions have to be used.  The description of the
handling, is not repeated in detail in this section since it is the
same as with ART1.  Only the parameters for the functions will be
mentioned here.


\paragraph*{ART2 Initialization Function}
\index{ART2!initialization function}

For an ART2 network the weights of the top-down-links
(\fz~$\rightarrow$ \fe~links) are set to 0.0 according to the
theory (\cite{CG87b}).

The choice of the initial bottom-up-weights is determined as follows:
if a pattern has been trained, then the next
presentation of the same pattern must not generate a new winning class.
On the contrary, the same \fz~unit should win, with a higher
activation than all the other recognition units.

This implies that the norm of the initial weight-vector has to be
smaller than the one it has after several training cycles.
If $J$ ($1 \leq J \leq M$) is the actual winning unit in \fz, then
equation~\ref{eq f1 f2 weights 4} is given by the theory:

\begin{equation}
   ||\mbox{{\bf z}}^J|| \rightarrow \left|\left| \frac{\mbox{{\bf u}}}{1-d}
                                    \right|\right|
                         = \frac{1}{1-d},
   \label{eq f1 f2 weights 4}
\end{equation}

where {\bf z}$^J$ is the the weight vector of the links from the
\fe~units to the $J$th \fz~unit and where d is a parameter, described
below.

If all initial values $z_{ij}(0)$ are presumed to be equal, this means:

\begin{equation}
  z_{ij}(0) \leq \frac{1}{(1-d) \sqrt{N}} \mbox{\hspace{1cm}}
                                        \forall \mms 1 \leq i \leq N,
                                                     1 \leq j \leq M.
  \label{eq f1 f2 weights 5}
\end{equation}

If equality is chosen in equation~\ref{eq f1 f2 weights 5}, then ART2 will
be as sensitive as possible.

To transform the inequality~\ref{eq f1 f2 weights 5} to an equation,
in order to compute values, we introduce another
parameter $\gamma$ and get:

\begin{equation}
  z_{ij}(0) = \frac{1}{\gamma (1-d) \sqrt{N}} \mbox{\hspace{1cm}}
                                        \forall \mms 1 \leq i \leq N,
                                                     1 \leq j \leq M,
  \label{eq f1 f2 weights 6}
\end{equation}

where $\gamma \geq 1$.

To initialize an ART2 network, the function {\tt ART2\_Weights} has to
be selected.  Specify the parameters d and $\gamma$ as the first and
second initialization parameter. (A description of parameter d is given
in the subsection on the ART2 learning function.)  Finally press the
\fbox{INIT}-button to initialize the net.

{\bf WARNING!} You should always use {\tt ART2\_Weights} to initialize
ART2 networks. When using another SNNS initialization function the
behavior of the simulator during learning is not predictable, because
not only the trainable links will be initialized, but also the fixed
weights of the network.



\paragraph*{ART2 Learning Function}
\index{ART2!learning function}

For the ART2 learning function {\tt ART2} there are various parameters
to specify. Here is a list of all parameters known from the theory:


\begin{tabbing}\hspace*{9mm}\= \kill
   
$\rho$ \> \begin{minipage}[t]{14cm}Vigilance parameter.  (first
parameter of the learning and update function).  $\rho$ is defined on
the interval $0 \leq \rho \leq 1.$ For some reason, described
in~\cite{Her92} only the following interval makes sense: $\frac{1}{2}
\sqrt{2} \leq \rho \leq 1.$\end{minipage}\\

$a$ \> \begin{minipage}[t]{14cm}Strength of the influence of the lower
level in \fe~by the middle level.  (second parameter of the learning
and update function).  Parameter $a$ defines the importance of the
expection of \fz, propagated to \fe: $a > 0.$ Normally a value of $a
\gg 1$ is chosen to assure quick stabilization in
\fe.\end{minipage}\\

$b$ \> \begin{minipage}[t]{14cm}Strength of the influence of the
middle level in \fe~by the upper level.  (third parameter of the
learning and update function).  For parameter $b$ things are similar
to parameter $a$.  A high value for $b$ is even more important,
because otherwise the network could become instable (\cite{CG87b}).
$b > 0, \mbox{normally:} b \gg 1.$\end{minipage}\\

$c$ \> \begin{minipage}[t]{14cm}Part of the length of vector {\bf p}
(units \pk{1} \dots \pk{N}) used to compute the error.  (fourth
parameter of the learning and update function).  Choose $c$ within $0
< c < 1$.\end{minipage}\\

$d$ \> \begin{minipage}[t]{14cm}Output value of the \fz~winner unit.
You won't have to pass $d$ to {\tt ART2}, because this parameter is
already needed for initialization. So you have to enter the value,
when initializing the network (see subsection on the initialization
function).  Choose $d$ within $0 < d < 1$.  The parameters $c$ and $d$
are dependent on each other.  For reasons of quick stabilization $c$
should be chosen as follows: $0 < c \ll 1$.  On the other hand $c$
and $d$ have to fit the following condition: $0 \ll \frac{cd}{1-d}
\leq 1.$ \end{minipage}\\

$e$ \> \begin{minipage}[t]{14cm}Prevents from division by zero. Since
this parameter does not help to solve essential problems, it is
implemented as a fix value within the SNNS source code.
\end{minipage}\\
 
$\Theta$ \> \begin{minipage}[t]{14cm}Kind of threshold. For $0 \leq
x,q \leq \Theta$ the activation values of the units \xk{i}~and
\qk{i}~only have small influence (if any) on the middle level of \fe.
The output function $f$ of the units \xk{i}~and \qk{i}~takes $\Theta$
as its parameter. Since this noise function is continuously
differentiable, it is called {\tt Out\_ART2\_Noise\_ ContDiff} in
SNNS.  Alternatively a piecewise linear output function may be used.
In SNNS the name of this function is {\tt Out\_ART2\_Noise\_PLin}.
Choose $\Theta$ within $0 \leq \Theta < 1.$\end{minipage}\\

\end{tabbing}

To train an ART2 network, make sure, you have chosen the learning
function {\tt ART2}.  As a first step initialize the network with the
initialization function {\tt ART2\_Weights} described above. Then set
the five parameters $\rho$, $a$, $b$, $c$ and $\Theta$, in the
parameter windows 1 to 5 in both the {\tt LEARN} and {\tt UPDATE}
lines of the control panel. Example values are 0.9, 10.0, 10.0, 0.1, and
0.0. Then select the number of learning cycles, and finally use the buttons
\fbox{SINGLE} and \fbox{ALL} to train a single pattern or all patterns
at a time, respectively.

\paragraph*{ART2 Update Functions}
\index{ART2!update functions}

Again two update functions for ART2 networks have been
implemented:

\begin{itemize}
\item {\tt ART2\_Stable}
\item {\tt ART2\_Synchronous}.
\end{itemize}

Meaning and usage of these functions are equal to their equivalents of
the ART1 model. For both of them the parameters $\rho$, $a$, $b$, $c$ and
$\Theta$ have to be defined in the row of update parameters in the
control panel.


\subsection{ARTMAP}
\label{artmap}
\index{ARTMAP}

\subsubsection{Structure of an ARTMAP Network}
\index{ARTMAP!structure}
\index{ARTMAP!topology}

Since an ARTMAP network is based on two networks of the ART1 model, it
is useful to know how ART1 is realized in SNNS. Having taken two of
the ART1 (\arta~and \artb) networks as they were defined in
section~\ref{art1}, we add several units that represent the
MAP field.  The connections between \arta~and the MAP field, \artb~and
the MAP field, as well as those within the MAP field are shown in
figure~\ref{artmap structure}.  The figure lacks the full connection
from the \fza~layer to the \fab~layer and those from each \fzb~unit to
its respective \fab~unit and vice versa.

\begin{figure}[hbtp]
 \begin{center}
  \begin{minipage}{\textwidth}
    \screendump{0.7}{nn_models/amapee.ps}
  \end{minipage}
  \caption{The MAP field with its control units.}
   \label{artmap structure}
 \end{center}
\end{figure}

The map field units represent the categories, onto which the
\arta~classes are mapped\footnote{Different \arta~classes may be
mapped onto the same category.}. The \G~unit is the MAP field gain
unit. The units \resm~(reset map), \rb~(reset \fzb), \rg~(reset
general), \rhog~(vigilance) and \de~(delay 1) represent the
inter-ART-reset control.  \drho~and \qu~(quotient) have to realize the
Match-Tracking-Mechanism and \cl~(classified) and \nc~(not
classifiable) again show whether a pattern has been {\em classified}
or was {\em not classifiable}.


\subsubsection{Using ARTMAP Networks in SNNS}
\label {ARTMAP}
\label{using artmap networks in snns}
\index{ARTMAP!usage}

\paragraph*{ARTMAP Initialization Function}
\index{ARTMAP!initialization function}

Since the trainable weights of an ARTMAP network are primarily the
ones of the two ART1 networks \arta~and \artb, it is easy to explain
the ARTMAP initialization function {\tt ARTMAP\_Weights.} To use this
function you have to select {\tt ARTMAP\_Weights} from the menu of the
initialization functions. For {\tt ARTMAP\_Weights} you have to set
the four parameters $\beta^a$, $\gamma^a$, $\beta^b$ and $\gamma^b$.
You can look up the meaning of each pair $\beta^?$, $\gamma^?$ in
section~\ref{using art1 networks in snns}, for the respective
ART$^?$-part of the network.


\paragraph*{ARTMAP Learning Function}
\index{ARTMAP!learning function}

Select the ARTMAP learning function {\tt ARTMAP} from the menu of the
learning functions. Specify the three parameters \rhoastart, \rhob~and
\rhog in the {\tt LEARN} row of the control panel. Example values could
be 0.7, 1.0, 1.0, and 0.0.  \rhoastart~is the initial vigilance
parameter for the \arta-part of the net, which may be modified by the
Match-Tracking-Mechanism.  \rhob~is the vigilance parameter for the
\artb-part and \rhog~is the one for the Inter-ART-Reset control.

\paragraph*{ARTMAP Update Functions}
\index{ARTMAP!update functions}

For ARTMAP two update functions have been implemented, as well:

\begin{itemize}
\item {\tt ARTMAP\_Stable}
\item {\tt ARTMAP\_Synchronous}.
\end{itemize}

{\tt ARTMAP\_Stable} is again used to propagate a pattern through the
network until a stable state is reached, while {\tt ARTMAP\_Synchronous}
does only perform one propagation step at a time. For both of the functions
the parameters \rhoastart, \rhob~and \rhog~have to be specified in the
line for update parameters of the control panel.
The usage is the same as it is for ART1 and ART2 networks.


\subsection{Topology of ART Networks in SNNS}
\label{topology of art networks in snns}
\index{ART!topology}

The following tables are an exact description of the topology requirements
for the ART models ART1, ART2 and ARTMAP.
For ARTMAP the topologies of the two ART1-parts of the net are the same
as the one shown in the ART1 table.


\index{ART2!topology}

\begin{center}
\begin{small}
\begin{tabular}{|l|c|l|l|l||l|l|} \hline
\multicolumn{7}{|c|}{{\bf ART2}} \\ \hline
\multicolumn{7}{l}{\vspace{5mm}} \\ \hline
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\multicolumn{5}{|c||}{{\bf unit definition}}
           & \multicolumn{2}{c|}{{\bf connections}} \\ \hline
%%%%%%%%%
\multicolumn{1}{|c}{unit} & \multicolumn{1}{|c}{top.} &
\multicolumn{1}{|c}{activation} & \multicolumn{1}{|c}{output} &
\multicolumn{1}{|c||}{site} & \multicolumn{1}{c}{target} &
\multicolumn{1}{|c|}{target} \\
%%%%%%%%%
\multicolumn{1}{|c}{name} & \multicolumn{1}{|c}{type} &
\multicolumn{1}{|c|}{function} & \multicolumn{1}{|c}{function}
& \multicolumn{1}{|c||}{names} & \multicolumn{1}{c}{unit} &
\multicolumn{1}{|c|}{site} \\
\hline
%%%%%%%%%%
\inp{i} & i & \actid & \outid & & \wk{i} & \\
& & & & & \rk{i} & \\ \hline
\wk{i} & h & \actartzid & \outid & & \xk{i} & \\ \hline
\xk{i} & h & {\tt Act\_ART2\_NormW} & {\em signal function}$^1$ & & \vk{i} & \\
\hline
\vk{i} & h & \actartzid & \outid & & \uk{i} & \\ \hline
\uk{i} & h & {\tt Act\_ART2\_NormV} & \outid & & \pk{i} & \\
& & & & & \wk{i} & \\ \hline
\pk{i} & h & \actartzid & \outid & & \qk{i} & \\
& & & & & \rk{i} & \\
& & & & & \rec{j} $\forall j$ & \\ \hline
\qk{i} & h & {\tt Act\_ART2\_NormP} & {\em signal function}$^1$ & & \vk{i} & \\
\hline
\rk{i} & h & {\tt Act\_ART2\_NormIP} & \outid & & & \\ \hline
\rec{j} & s & {\tt Act\_ART2\_Rec} & \outid & & \pk{i} $\forall i$ & \\
& & & & & \rst{j} & \\ \hline
\rst{j} & h & {\tt Act\_ART2\_Rst} & \outid & & \rec{j} & \\
\hline
\multicolumn{7}{|l|}{$^1$ either {\tt Out\_ART2\_Noise\_ContDiff}
                     or {\tt Out\_ART2\_Noise\_PLin}.} \\
\hline
\end{tabular}
\end{small}
\end{center}

\clearpage


\index{ARTMAP!topology}

\begin{center}
\begin{small}
\begin{tabular}{|l|c|l|l|l||l|l|}
\hline
%%%%%%%%%
\multicolumn{7}{|c|}{{\bf ARTMAP}} \\
\hline
\multicolumn{7}{l}{\vspace{5mm}} \\
\hline
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\multicolumn{5}{|c||}{{\bf site definition}} & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{site name} & \multicolumn{2}{c||}{site function}
      & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{{\tt ARTa\_G}}
      & \multicolumn{2}{c||}{{\tt Site\_at\_least\_1}}
      & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{{\tt ARTb\_G}}
      & \multicolumn{2}{c||}{{\tt Site\_at\_least\_1}}
      & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{{\tt ARTb\_rb}}
      & \multicolumn{2}{c||}{{\tt Site\_WeightedSum}}
      & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{{\tt rho\_rb}}
      & \multicolumn{2}{c||}{{\tt Site\_WeightedSum}}
      & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{{\tt npa\_qu}}
      & \multicolumn{2}{c||}{{\tt Site\_Reciprocal}}
      & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{{\tt cmpa\_qu}}
      & \multicolumn{2}{c||}{{\tt Site\_WeightedSum}}
      & \multicolumn{2}{l|}{} \\
\cline{1-7}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hline
\multicolumn{7}{l}{\vspace{5mm}} \\
\hline
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\multicolumn{5}{|c||}{{\bf unit definition}}
       & \multicolumn{2}{c|}{{\bf connections}} \\
\hline
%%%%%%%%%
\multicolumn{1}{|c}{unit} & \multicolumn{1}{|c}{top.} &
\multicolumn{1}{|c}{activation} & \multicolumn{1}{|c}{output} &
\multicolumn{1}{|c||}{site} & \multicolumn{1}{c}{target} &
\multicolumn{1}{|c|}{target} \\
%%%%%%%%%
\multicolumn{1}{|c}{name} & \multicolumn{1}{|c}{type} &
\multicolumn{1}{|c|}{function} & \multicolumn{1}{|c}{function}
& \multicolumn{1}{|c||}{names} & \multicolumn{1}{c}{unit} &
\multicolumn{1}{|c|}{site} \\
\hline
%%%%%%%%%%
\map{j} & h & {\tt Act\_at\_least\_2} & \outid & & {\bf rm} & \\
\hline
%%%%%%%%%%
{\bf cl} & h & {\tt Act\_at\_least\_2} & \outid & & & \\
\hline
%%%%%%%%%%
{\bf nc} & h & {\tt Act\_at\_least\_1} & \outid & & & \\
\hline
%%%%%%%%%%
{\bf G} & h & {\tt Act\_exactly\_1} & \outid & {\tt ARTa\_G} &
             \map{j} $\forall j$ & \\
& & & & {\tt ARTb\_G} & & \\
\hline
%%%%%%%%%%
\de & h & \actid & \outid & & {\bf rb} & {\tt ARTb\_rb} \\
\hline
%%%%%%%%%%
{\bf rb} & h & {\tt Act\_Product} & \outid & {\tt ARTb\_rb} & {\bf rg} & \\
& & & & {\tt rho\_rb} & & \\
\hline
%%%%%%%%%%
{\bf rm} & h & \actid & \outid & & {\bf rg} & \\
\hline
%%%%%%%%%%
{\bf rg} & h & {\tt Act\_less\_than\_0} & \outid & & {\bf drho} & \\
& & & & & {\bf cl} & \\
\hline
%%%%%%%%%%
{\bf rho} & h & \actid & \outid & & {\bf rho} & \\
& & & & & {\bf rb} & {\tt rho\_rb} \\
\hline
%%%%%%%%%%
{\bf qu} & h & {\tt Act\_Product} & \outid & {\tt inpa\_qu} &
        {\bf drho} & \\
& & & & {\tt cmpa\_qu} & & \\
\hline
%%%%%%%%%%
{\bf drho} & h & {\tt Act\_ARTMAP\_DRho} & \outid & & {\bf drho} & \\
& & & & & {\bf rho$^a$} & \\
\hline
%%%%%%%%%%
\inpa{i} & \multicolumn{4}{|c||}{see ART1 table} & {\bf qu} &
            {\tt inpa\_qu} \hspace*{8mm} \\
\hline
%%%%%%%%%%
\cmpa{i} & \multicolumn{4}{|c||}{see ART1 table} & {\bf qu} &
            {\tt cmpa\_qu} \\
\hline
%%%%%%%%%%
\reca{i} & \multicolumn{4}{|c||}{see ART1 table} &  {\bf G} &
            {\tt ARTa\_G} \\
\hline
%%%%%%%%%%
\recb{i} & \multicolumn{4}{|c||}{see ART1 table} &  {\bf G} &
            {\tt ARTb\_G} \\
\hline
%%%%%%%%%%
\delb{i} & \multicolumn{4}{|c||}{see ART1 table} &  \de &  \\
\hline
%%%%%%%%%%
\cla & \multicolumn{4}{|c||}{see ART1 table} &  {\bf cl} & \\
\hline
%%%%%%%%%%
\clb & \multicolumn{4}{|c||}{see ART1 table} &  {\bf cl} & \\
& \multicolumn{4}{|c||}{} & {\bf drho} & \\
\hline
%%%%%%%%%%
\nca & \multicolumn{4}{|c||}{see ART1 table} &  {\bf nc} & \\
\hline
%%%%%%%%%%
\ncb & \multicolumn{4}{|c||}{see ART1 table} &  {\bf nc} & \\
\hline
%%%%%%%%%%
\rga & \multicolumn{4}{|c||}{see ART1 table} &  {\bf drho} & \\
\hline
%%%%%%%%%%
{\bf rho}$^a$ & \multicolumn{4}{|c||}{see ART1 table} &  {\bf drho} & \\
\hline
%%%%%%%%%%
\end{tabular}
\end{small}
\end{center}

\clearpage

\index{ART1!topology}
\index{ARTMAP!topology}
%\vspace*{5mm}

\begin{center}
\begin{small}
\begin{tabular}{|l|c|l|l|l||l|l|}
\hline
%%%%%%%%%
\multicolumn{7}{|c|}{{\bf ART1 and ART1-parts of ARTMAP (\arta, \artb)}} \\
\hline
\multicolumn{7}{l}{\vspace{5mm}} \\
\hline
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\multicolumn{5}{|c||}{{\bf site definition}} & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{site name} & \multicolumn{2}{c||}{site function}
      & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{{\tt rst\_self}}
      & \multicolumn{2}{c||}{{\tt Site\_WeightedSum}}
      & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{{\tt rst\_signal}}
      & \multicolumn{2}{c||}{{\tt Site\_at\_least\_2}}
      & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{{\tt inp\_g1}}
      & \multicolumn{2}{c||}{{\tt Site\_at\_least\_1}}
      & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{{\tt rec\_g1}}
      & \multicolumn{2}{c||}{{\tt Site\_at\_most\_0}}
      & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{{\tt inp\_ri}}
      & \multicolumn{2}{c||}{{\tt Site\_WeightedSum}}
      & \multicolumn{2}{l|}{} \\
\cline{1-5}
%%%%%%%%%
\multicolumn{3}{|c|}{{\tt rho\_ri}}
      & \multicolumn{2}{c||}{{\tt Site\_WeightedSum}}
      & \multicolumn{2}{l|}{} \\
\cline{1-7}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hline
\multicolumn{7}{l}{\vspace{5mm}} \\
\hline
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%
\multicolumn{5}{|c||}{{\bf unit definition}} &
        \multicolumn{2}{c|}{{\bf connections}} \\
\hline
%%%%%%%%%
\multicolumn{1}{|c}{unit} & \multicolumn{1}{|c}{top.} &
\multicolumn{1}{|c}{activation} & \multicolumn{1}{|c}{output} &
\multicolumn{1}{|c||}{site-} & \multicolumn{1}{c}{target} &
\multicolumn{1}{|c|}{target} \\
%%%%%%%%%
\multicolumn{1}{|c}{name} & \multicolumn{1}{|c}{type} &
\multicolumn{1}{|c|}{function} & \multicolumn{1}{|c}{function}
& \multicolumn{1}{|c||}{names} & \multicolumn{1}{c}{unit} &
\multicolumn{1}{|c|}{site} \\
\hline
%%%%%%%%%%
\inp{i} & i & \actid & \outid & & \cmp{i} &  \\
& & & & & \geu &      {\tt inp\_g1} \\
& & & & & {\bf ri} & {\tt inp\_ri} \\
& & & & & \gzu & \\
\hline
%%%%%%%%%%%
\cmp{i} & h & {\tt Act\_at\_least\_2} & \outid & & \rec{j} $\forall j$ & \\
& & & & & {\bf rc} & \\
\hline
%%%%%%%%%%%
\rec{j} & s & \actid & \outid & & \del{j} & \\
& & & & & \geu & {\tt rec\_g1} \\
\hline
%%%%%%%%%%%
\del{j} & h & {\tt Act\_at\_least\_2} & \outid & & \cmp{i} $\forall i$ & \\
& & & & & {\bf d}$_1$  & \\
& & & & & \rst{j} & {\tt rst\_signal} \\
\hline
%%%%%%%%%%%
{\bf d}$_1$ & h & {\tt Act\_at\_least\_1} & \outid & & {\bf d}$_2$ & \\
\hline
%%%%%%%%%%%
{\bf d}$_2$ & h & {\tt Act\_at\_least\_1} & \outid & & {\bf d}$_3$ & \\
\hline
%%%%%%%%%%%
{\bf d}$_3$ & h & {\tt Act\_at\_least\_1} & \outid & & {\bf cl} & \\
\hline
%%%%%%%%%%%
\rst{j} & h & {\tt Act\_at\_least\_1} & \outid & {\tt rst\_self} &
          \rst{j} & {\tt rst\_self} \\
& & & & {\tt rst\_signal} & \rec{j} & \\
\hline
%%%%%%%%%%%
{\bf cl} & h & {\tt Act\_at\_least\_1} & \outid & & & \\
\hline
%%%%%%%%%%%
{\bf nc} & h & {\tt Act\_ART1\_NC} & \outid & & & \\
& & for ARTMAP: & & & & \\
& & {\tt Act\_ARTMAP\_NCa}, & & & & \\
& & {\tt Act\_ARTMAP\_NCb} & & & & \\
\hline
%%%%%%%%%%%
\geu & h & {\tt Act\_at\_least\_2} & \outid & {\tt inp\_g1} &
            \cmp{i} $\forall i$ & \\
& & & & {\tt rec\_g1} & & \\
\hline
%%%%%%%%%%%
\gzu & h & {\tt Act\_at\_most\_0} & \outid & & \rec{j} $\forall j$ & \\
& & & & & {\bf cl} & \\
\hline
%%%%%%%%%%%
{\bf ri} & h & {\tt Act\_Product} & \outid & {\tt inp\_ri} &
           {\bf rg} & \\
& & & & {\tt rho\_ri} & & \\
\hline
%%%%%%%%%%%
{\bf rc} & h & \actid & \outid & & {\bf rg} & \\
\hline
%%%%%%%%%%%
{\bf rg} & h & {\tt Act\_less\_than\_0} & \outid & & \rec{j} $\forall j$ & \\
& & & & & \rst{j} $\forall j$ & {\tt rst\_signal} \\
& & & & & {\bf cl} & \\
\hline
%%%%%%%%%%%
{\bf rho} & h & \actid & \outid & & {\bf rho} & \\
& & & & & {\bf ri} & {\tt rho\_ri} \\
\hline
%%%%%%%%%%%
\end{tabular}
\end{small}
\end{center}

\clearpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% RESET FRACTION values to original values
% ========================================
\renewcommand{\topfraction}[0]{.7}
\renewcommand{\bottomfraction}[0]{.3}
\renewcommand{\textfraction}[0]{.2}
\renewcommand{\floatpagefraction}[0]{.5}




\section{Self-Organizing Maps (SOMs)}
\index{Kohonen Feature Maps}
\index{SOMs}
\index{Self Organizing Maps}
\label{SOMchap}
 
\subsection{SOM Fundamentals}

The Self-Organizing Map (SOM) algorithm of Kohonen, also called
Kohonen feature map, is one of the best known artificial neural
network algorithms. In contrast to most other algorithms in SNNS, it
is based on unsupervised learning. SOMs are a unique class of neural
networks, since they construct topology-preserving mappings of the
training data where the location of a unit carries semantic
information. Therefore, the main application of this algorithm is
clustering of data, obtaining a two-dimensional display of the input
space that is easy to visualize.

Self-Organizing Maps consist of two layers of units: A one dimensional
input layer and a two dimensional competitive layer, organized as a 2D
grid of units. This layer can neither be called hidden nor output
layer, although the units in this layer are listed as hidden units
within SNNS. Each unit in the competitive layer holds a weight
(reference) vector, $W_i$, that, after training, resembles a different
input pattern.  The learning algorithm for the SOM accomplishes two
important things:

\begin{enumerate}
\item clustering the input data 
\item spatial ordering of the map so that similar input patterns
tend to produce a response in units that are close to each other in the grid.
\end{enumerate} 

Before starting the learning process, it is important to initialize the
competitive layer with normalized vectors.  The input pattern vectors
are presented to all competitive units in parallel and the best
matching (nearest) unit is chosen as the winner.  Since the vectors
are normalized, the
similarity between the normalized input vector X = $(x_i)$ and the
reference units $W_j$ = $(w_{ij})$ can be calculated using the dot
product:

$$Net_j(t) = X \cdot W_j = \sum_{i=1}^n x_i(t) w_{ij}(t) $$

The vector\footnote{ $c$ will be used as index for the winning
unit in the competitive layer throughout this text} $W_c$ most similar to
$X$ is the one with the largest dot product with $X$:

$$Net_c(t) = \max_j \{ Net_j(t) \} = X\cdot W_c$$

The topological ordering is achieved by using a spatial neighborhood
relation between the competitive units during learning. I.e. not only
the best-matching vector, with weight $W_c$, but also its neighborhood
\footnote{Neighborhood is defined as the set of units within a
certain radius of the winner. So $N(1)$ would be the the eight direct
neighbors in the 2D grid; $N(2)$ would be $N(1)$ plus the 16 next
closest; etc.} $N_c$, is adapted, in contrast to a basic competitive
learning algorithm like LVQ:

\begin{eqnarray*}
\Delta w_{ij}(t) & = & e_j(t)\cdot(x_i(t)-w_{ij}(t)) }\hfill{ \hbox{~~for}\:j\in N_c\\ 
\Delta w_{ij}(t) & = & 0 }\hfill{ \hbox{~~for}\:j \not\in N_c\\
\end{eqnarray*}
where

~$e_j(t) = h(t) \cdot e^{-(d_j/r(t))^2}$~~(Gaussian Function)\\
\begin{tabular}{ll}
$d_j$:     & distance between $W_j$ and winner $W_c$\\
$h(t)$:    & adaptation height at time t with $0\leq h(t)\leq 1$\\
$r(t)$:    & radius of the spatial neighborhood $N_c$ at time t\\
\end{tabular} 
 
The adaption height and radius are usually decreased over time to
enforce the clustering process.

See \cite{Koh88} for a more detailed description of SOMs and their
theory. 



\subsection{SOM Implementation in SNNS}

SNNS originally was not designed to handle units whose location carry
semantic information. Therefore some points have to be taken care of
when dealing with SOMs.  For learning it is necessary to pass the
horizontal size of the competitive layer to the learning function,
since the internal representation of a map is different from its
appearance in the display. Furthermore it is not recommended to use
the graphical network editor to create or modify any feature maps.
The creation of new feature maps should be carried out with the {\bf
BIGNET (Kohonen)} creation tool (see chapter
\ref{Bignet}).

\subsubsection{The KOHONEN Learning Function}

SOM training in SNNS can be performed with the learning function
{\tt Kohonen}. It can be selected from the list of learning functions
in the control panel. Five parameters have to be passed to this
learning function:

\begin{itemize}

\item {\bf Adaptation Height (Learning Height)} 
The initial adaptation height $h(0)$ can vary between 0 and 1. It determines
the overall adaptation strength.

\item {\bf Adaptation Radius (Learning Radius)} 
The initial adaptation radius $r(0)$ is the radius of the neighborhood
of the winning unit. All units within this radius are adapted. Values
should range between 1 and the size of the map.

\item {\bf Decrease Factor mult\_H}
The adaptation height decreases monotonically after the presentation
of every learning pattern. This decrease is controlled by the decrease
factor mult\_H: $h(t+1) := h(t) \cdot mult\_H$

\item {\bf Decrease Factor mult\_R}
The adaptation radius also decreases monotonically after the
presentation of every learning pattern. This second decrease is
controlled by the decrease factor mult\_R: $r(t+1) := r(t) * mult\_R$

\item {\bf Horizontal size} 
Since the internal representation of a network doesn't allow to
determine the 2-dimensional layout of the grid, the horizontal size in
units must be provided for the learning function.  It is the same
value as used for the creation of the network.
\end{itemize}

{\bf Note:} After each completed training the parameters adaption
height and adaption radius are updated in the control panel to reflect
their new values. So when training is started anew, it resumes at the
point where it was stopped last. Both mult\_H and mult\_R should be in
the range $(0,1]$. A value of 1 consequently keeps the adaption values
at a constant level.


\subsubsection{The Kohonen Update Function}

A special update function ({\tt Kohonen\_Order}) is also provided in
SNNS. This function has to be used since it is the only one that takes
care of the special ordering of units in the competitive layer. If
another update is selected an ``Error: Dead units in the network'' may
occur when propagating patterns.

\subsubsection{The Kohonen Init Function}

Before a SOM can be trained, its weights have to be initialized using
the init function {\tt Kohonen\_\-Weights}. This init function first
initializes all weights with random values between the specified
borders. Then it normalizes all links on a per-unit basis. Some of
the internal values needed for later training are also set here. It
uses the same parameters as {\tt CPN\_Weights} (see section
\ref{CountPropInit}). 


\subsubsection{The Kohonen Activation Functions}

The Kohonen learning algorithm does not use the activation functions
of the units. Therefore it is basically unimportant which activation
function is used in the SOM. For display and evaluation reasons,
however, the two activation functions {\tt Act\_Component} and {\tt
Act\_Euclid} have been implemented in SNNS. {\tt Act\_Euclid} copies
the Euclidian distance of the unit from the training pattern to the
unit activation, while  {\tt Act\_Component} writes the weight to one
specific component unit into the activation of the unit. 


\subsubsection{Building and Training Self-Organizing Maps}

Since any modification of a Self-Organizing Map in the 2D display like
the creation, deletion or movement of units or weights may destroy the
relative position of the units in the map we strongly recommend to
generate these networks only with the available {\bf BIGNET (Kohonen)}
tool.  See also chapter \ref{Bignet} for detailed information on how
to create networks.  Outside xgui you can also use the tool {\bf
convert2snns}.  Information on this program can be found in the
respective README file in the directory SNNSv3.3/tools/doc.  Note: Any
modification of the units after the creation of the network may result
in undesired behavior!

To train a new feature map with SNNS, set the appropriate standard
functions: select init function {\bf KOHONEN\_Weights}, update
function {\bf Kohonen\_Order} and learning function {\bf Kohonen}.
Remember: There is no special activation function for Kohonen
learning, since setting an activation function for the units doesn't
affect the learning procedure. To visualize the results of the
training, however, one of the two activation functions {\tt
Act\_Euclid} and {\tt Act\_Componnent} has to be selected. For their 
semantics see section~\ref{SOMEva}.

After providing patterns (ideally normalized) and assigning
reasonable values to the learning function, the learning process can
be started.  To get a proper appearance of SOMs in the 2D-display set
the {\bf grid width} to 16 and turn off the unit labeling and link
display in the display panel.

When a learning run is completed the adaption height and adaption
radius parameters are automatically updated in the control panel to
reflect the actual values in the kernel.


\subsubsection{Evaluation Tools for SOMs}
\label{SOMEva}

When the results of the learning process are to be analyzed, the tools
described here can be used to evaluate the qualitative properties of
the SOM.  In order to provide this functionality, a special panel was
added. It can be called from the manager panel by clicking the \fbox{\tt
KOHONEN} button and is displayed in figure \ref{Kopa}. Yet, the panel can
only be used in combination with the control panel.


\begin{figure}[htbp]
\begin{center}
  \begin{minipage}{\textwidth}
    \screendump{0.5}{nn_models/kohonen_panel.ps}
  \end{minipage}
\caption{The additional KOHONEN (control) panel}
\label{Kopa}
\end{center}
\end{figure}

\begin{enumerate}

\item {\bf Euclidian distance}\\ 
The distance between an input vector and the weight vectors can be
visualized using a distance map. This function allows using the SOM as
a classifier for arbitrary input patterns: Choose {\bf Act\_Euclid} as
activation function for the hidden units, then use the \fbox{TEST}
button in the control panel to see the distance maps of consecutive
patterns. As green squares (big filled squares on B/W terminals)
indicate high activations, green squares here mean big distances,
while blue squares represent small distances.  Note: The input vector
is not normalized before calculating the distance to the competitive
units. This doesn't affect the qualitative appearance of the distance
maps, but offers the advantage of evaluating SOMs that were generated
by different SOM-algorithms (learning without normalization).  If the
dot product as similarity measure is to be used select {\bf
Act\_Identity} as activation function for the hidden units.

\item {\bf Component maps} \\
To determine the quality of the clustering for each component of the
input vector use this function of the SOM analyzing tool. Due to the
topology-preserving nature of the SOM algorithm, the component maps
can be compared after printing, thereby detecting correlations between
some components: Choose the activation function {\bf Act\_Component}
for the hidden units. Just like displaying a pattern, component maps
can be displayed using the {\bf LAYER} buttons in the {\bf KOHONEN}
panel. Again, green squares represent large, positive weights.

\item {\bf Winning Units} \\
The set of units that came out as winners in the learning process can
also be displayed in SNNS. This shows the distribution of patterns on
the SOM.  To proceed, turn on {\bf units top} in the setup window of
the display and select the {\bf winner} item to be shown. New winning
units will be displayed without deleting the existing, which enables
tracing the temporal development of clusters while learning is in
progress.  The display of the winning units is refreshed by pressing
the \fbox{WINNER} button again.

{\bf Note:} Since the winner algorithm is part of the KOHONEN
learning function, the learning parameters must be set as if learning
is to be performed.

\end{enumerate}


\section{Autoassociative Networks}
\index{Autoassociative Networks}
\label{AAchap}
 
\subsection{General Characteristics}

Autoassociative networks store single instances of items, and can be
thought of in a way similar to human memory. In an autoassociative
network each pattern presented to the network serves as both the input
and the output pattern.  Autoassociative networks are typically used
for tasks involving pattern completion.  During retrieval, a probe
pattern is presented to the network causing the network to display a
composite of its learned patterns most consistent with the new
information.

Autoassociative networks typically consist of a single layer of nodes
with each node representing some feature of the environment. However
in SNNS they are represented by two layers to make it easier to
compare the input to the output.  The following section explains the
layout in more detail\footnote{For any comments or questions
concerning the implementation of an autoassociative memory please
refer to Jamie DeCoster at jamie@psych.purdue.edu}.

Autoassociative networks must use the update function {\tt
RM\_Synchronous} and the initialization function {\tt
RM\_Random\_Weights}. The use of others may destroy essential
characteristics of the autoassociative network. Please note, that the
update function {\tt RM\_Synchronous} needs as a parameter the number
of iterations performed before the network output is computed. 50 has
shown to be very suitable here.

All the implementations of autoassociative networks in SNNS report
error as the sum of squared error between the input pattern on the
world layer and the resultant pattern on the learning layer after the
pattern has been propagated a user defined number of times.


\subsection{Layout of Autoassociative Networks}

An autoassociative network in SNNS consists of two layers: A layer of
{\bf world} units and a layer of {\bf learning} units.  The
representation on the world units indicates the information coming
into the network from the outside world.  The representation on the
learning units represents the network's current interpretation of
the incoming information.  This interpretation is determined partially
by the input and partially by the network's prior learning.

Figure~\ref{AutoAssoz} shows a simple example network. Each unit in the
world layer sends input to exactly one unit in the learning layer.
The connected pair of units corresponds to a single node in the
typical representation of autoassociative networks.  The link from the
world unit always has a weight of 1.0, and is unidirectional from the
world unit to the learning unit.  The learning units are fully
interconnected with each other.


\begin{figure}[htbp]
\begin{center}
  \begin{minipage}{\textwidth}
    \screendump{0.7}{nn_models/auto_assoz_net.ps}
  \end{minipage}
\caption{A simple Autoassociative Memory Network}
\label{AutoAssoz}
\end{center}
\end{figure}


The links between the learning units change according to the selected
learning rule to fit the representation on the world units.  The links
between the world units and their corresponding learning units are not
affected by learning.


\subsection{Hebbian Learning}
\index{Hebbian Learning}

In Hebbian learning weights between learning nodes are adjusted so
that each weight better represents the relationship between the nodes.
Nodes which tend to be positive or negative at the same time will have
strong positive weights while those which tend to be opposite will
have strong negative weights.  Nodes which are uncorrelated will have
weights near zero.

The general formula for Hebbian learning is

\begin{displaymath}
  \Delta w_{ij} = n * input_i * input_j
\end{displaymath}

where:

\begin{tabular}{ll}
  $n$           &is the learning rate\\
  $input_i$     &is the external input to node i\\
  $input_j$     &is the external input to node j\\
\end{tabular}                                                    


\subsection{McClelland \& Rumelhart's Delta Rule}
\index{Delta Rule}

This rule is presented in detail in chapter 17 of \cite{rum861}.  In
general the delta rule outperforms the Hebbian learning rule.  The
delta rule is also less likely so produce explosive growth in the
network.  For each learning cycle the pattern is propagated through
the network ncycles (a learning parameter) times after which learning
occurs. Weights are updated according to the following rule:


\begin{displaymath}
  \Delta w_{ij} = n * d_i * a_j
\end{displaymath}

where:

\begin{tabular}{ll}
  $n$           &is the learning rate\\
  $a_j$         &is the activation of the source node\\
  $d_i$         &is the error in the destination node.\\
                &This error is defined as the external input - the
                internal input.\\
\end{tabular}                                                    
   
In their original work McClelland and Rumelhart used an unusual activation
function:

\begin{verbatim}
         for unit i, 
             if neti > 0
                delta ai = E * neti * (1 - ai) - D * ai
             else 
                delta ai = E * neti * (ai + 1) - D * ai
\end{verbatim}

where:

\begin{tabular}{ll}
  $neti$        &is the net input to i (external + internal)\\
  $E$           &is the excitation parameter (here set to 0.15)\\
  $D$           &is the decay parameter (here set to 0.15)\\
\end{tabular}                                                    

This function is included in SNNS as {\tt ACT\_RM}.  Other activation
functions may be used in its place.

\clearpage

\section{Partial Recurrent Networks}
\subsection{Models of Partial Recurrent Networks}

\subsubsection{Jordan Networks}
\index{Jordan Networks}

\begin{figure}[htbp]
 \begin{center}
  \begin{minipage}[htbp]{\textwidth}
   \screendump{0.6}{nn_models/jordan_net.ps}
  \end{minipage}
  \caption{Jordan network} 
  \label{jordan_net}
 \end{center}
\end{figure}

Literature: \cite{Jordan86a}, \cite{Jordan86b}

%\clearpage

\subsubsection{Elman Networks}

\begin{figure}[htbp]
 \begin{center}
  \begin{minipage}[htbp]{\textwidth}
   \screendump{0.7}{nn_models/elman_net.eps}
  \end{minipage}
  \caption{Elman network} 
 \end{center}
\end{figure}

Literature: \cite{Elman90}

\subsubsection{Extended Hierarchical Elman Networks}

\begin{figure}[htbp]
 \begin{center}
  \begin{minipage}[htbp]{\textwidth}
   \screendump{0.7}{nn_models/ext_elman.eps}
  \end{minipage}
  \caption{Extended Elman architecture} 
  \label{ext_elman_net}
 \end{center}
\end{figure}

\subsection{Working with Partial Recurrent Networks}

In this subsection, the initialization, learning, and update functions
for partial recurrent networks are described. These functions can not
be applied to only the three network models described in the previous
subsection. They can be applied to a broader class of partial
recurrent networks. Every partial recurrent network, that has the
following restrictions, can be used:

\begin{itemize}
\item If after the deletion of all context units and the links to and
from them, the remaining network is a simple feedforward architecture
with no cycles.
 
\item Input units must not get input from other units.
 
\item Output units may only have outgoing connections to context
units, but not to other units.
 
\item Every unit, except the input units, has to have at least one
incoming link. For a context unit this restriction is already
fulfilled when there exists only a self recurrent link. In this
case the context unit receives its input only from itself.
\end{itemize}

In such networks all links leading to context units are considered as
recurrent links.

Thereby the user has a lot of possibilities to experiment with a great
variety of partial recurrent networks. E.g. it is allowed to connect
context units with other context units.

{\bf Note:} context units are realized as special hidden units. All
units of type special hidden are assumed to be context units and are
treated like this.


\subsubsection{The Initialization Function JE\_Weights}  

The initialization function {\tt JE\_Weights} requires the
specification of five parameters:
 
\begin{itemize}
 \item \makebox[0.7cm][l]{$\alpha$, $\beta$} : 
       The weights of the forward connections are randomly chosen
       from the interval $[\alpha\,;\beta]$.  
 \item \makebox[0.7cm][l]{$\lambda$} : 
       Weights of self recurrent links from context units to themselves.
       Simple Elman networks use $\lambda = 0$. 
 \item \makebox[0.7cm][l]{$\gamma$} :
       Weights of other recurrent links to context units. This value
       is often set to $1.0$. 
 \item \makebox[0.7cm][l]{$\psi$}  : 
       Initial activation of all context units.
\end{itemize}

These values are to be set in the {\tt INIT} line of the control panel
in the order given above.


\subsubsection{Learning Functions}

By deleting all recurrent links in a partial recurrent network, a
simple feedforward network remains. The context units have now the 
function of input units, i.e. the total network input consists
of two components. The first component is the pattern vector, which
was the only input to the partial recurrent network. The second
component is a state vector. This state vector is given through the
next--state function in every step. By this way the behavior of a
partial recurrent network can be simulated with a simple feedforward
network, that receives the state not implicitly through recurrent
links, but as an explicit part of the input vector. In this sense,
backpropagation algorithms can easily be modified for the training of
partial recurrent networks in the following way:

\begin{enumerate}
 \item Initialization of the context units. In the following steps, all
       recurrent links are assumed to be not existent, except in step
       2(f). 
 \item Execute for each pattern of the training sequence the following
       steps:
       \begin{itemize}
        \item input of the pattern and forward propagation through the
              network  
        \item calculation of the error signals of output units by comparing
              the computed output and the teaching output
        \item back propagation of the error signals 
        \item calculation of the weight changes
        \item only on--line training: weight adaption
        \item calculation of the new state of the context units according
              to the incoming links
       \end{itemize}
 \item Only off--line training: weight adaption
\end{enumerate}

In this manner, the following learning functions have been adapted for
the training of partial recurrent networks like Jordan and Elman
networks: 

\begin{itemize}
\item {\tt JE\_BP}:  Standard Backpropagation for partial recurrent
networks 
\index{Learning!Function!JE\_BP}

\item {\tt JE\_BPMomentum}:  Standard Backpropagation with
Momentum--Term for partial recurrent networks 
\index{Learning!Function!JE\_BPMomentum}
 
\item {\tt JE\_Quickprop}: Quickprop for partial recurrent networks
\index{Learning!Function!JE\_Quickprop}
 
\item {\tt JE\_Rprop}: Rprop for partial recurrent networks
\index{Learning!Function!JE\_Rprop}
\end{itemize} 

The parameters for these learning functions are the same as for the
regular feedforward versions of these algorithms (see section
\ref{LearningParameters}) plus one special parameter. 

For training a network with one of these functions a method called teacher
forcing can be used. Teacher forcing means that during the training phase
the output units propagate the teaching output instead of their produced output
to successor units (if there are any). The new parameter is used
to enable or disable teacher forcing. If the value is less or equal 0.0
only the teaching output is used, if it is greater or equal 1.0 the real output
is propagated. Values between 0.0 and 1.0 yield a weighted sum of the 
teaching output and the real output. 

\subsubsection{Update Functions}

Two new update functions have been implemented for partial recurrent
networks:

\begin{itemize}

\item {\tt JE\_Order}:\\ 
This update function propagates a pattern from the input layer to the
first hidden layer, then to the second hidden layer, etc. and finally
to the output layer. After this follows a synchronous update of all
context units.

\item {\tt JE\_Special}:\\
This update function can be used for iterated long-term predictions. If
the actual prediction value $p_{i}$ is part of the next input pattern
$inp_{i+1}$ to predict the next value $p_{i+1}$, the input pattern
$inp_{i+1}$ can not be generated before the needed prediction value
$p_{i}$ is available.  For long-term predictions many input patterns
have to be generated in this manner. To generate these patterns
manually means a lot of effort.

Using the update function {\tt JE\_Special} these input patterns will
be generated dynamically. Let $n$ be the number of input units and $m$
the number of output units of the network.  {\tt JE\_Special}
generates the new input vector with the output of the last $n-m$ input
units and the outputs of the $m$ output units. The usage of this
update function requires $n > m$. The propagation of the new generated
pattern is done like using {\tt JE\_Update}.  The number of the actual
pattern in the control panel has no meaning for the input pattern when
using {\tt JE\_Special}.
\end{itemize}


\section{Stochastic Learning Functions}
\index{Stochastic Learning Functions}

The monte carlo method and simulated annealing are widely used
algorithms for solving any kind of optimization problems.  These
stochastic functions have some advantages over other learning
functions.  They allow any net structure, any type of neurons and any
type of error function. Even every neuron of a net could have another
learning function and any number of links.

\subsection{Monte-Carlo}
\index{Learning!Function!Monte-Carlo}

Monte-Carlo learning is an easy way to determine weights and biases of
a net. At every learning cycle all weights and biases are chosen by
random in the Range $[Min, Max]$. Then the error is calculated as
summed squared error of all patterns. If the error is lower than the
previous best error, the weights and biases are stored. This method is
not very efficient but useful for finding a good start point for
another learning algorithm.

\subsection{Simulated Annealing}
\index{Learning!Function!Simulated Annealing}

Simulated annealing is a more sophisticated method for finding the
global minima of a error surface. In contrast to monte carlo learning
only one weight or bias is changed at a learning cycle. Dependant on
the error development and a system temperature this change is
accepted or rejected.  One of the advantages of simulated annealing is
that learning does not get stuck in local minima.


At the beginning of learning the temperature $T$ is set to $T_0$. Each
training cycle consists of the following four steps.


\begin{enumerate}

\item Change one weight or bias by random in the range $[ Min, Max]$.

\item Calculate the net error as sum of the given error function for
all patterns.

\item Accept change if the error decreased or if the error increased
  by $\Delta E$ with the probability p given by: $ p = \exp \left(
  \frac{ - \Delta E}{T} \right)$

\item Decrease the temperature: $T = T \cdot deg$
\end{enumerate}

The three implemented simulated annealing functions only differ in
the way the net error is calculated. Sim\_Ann\_SS calculates a
summed squared error like the backpropagation learning functions;
Sim\_Ann\_WTA calculates a winner takes all error; and Sim\_Ann\_WWTA
calculates a winner takes all error and adds a term corresponding to
the security of the winner takes all decision.


\section{Scaled Conjugate Gradient (SCG)}
\index{Scaled Conjugate Gradient}
\index{SCG}


SCG \cite{MOLLER93} is a supervised learning algorithm for feedforward neural
networks, and is a member of the class of conjugate gradient methods. Before
describing SCG, we recall some key points concerning these methods. Eventually
we will discuss the parameters (virtually none) and the complexity of SCG.


\subsection{Conjugate Gradient Methods (CGMs)}

They are general purpose second order techniques that help minimize goal
functions of several variables, with sound theoretical foundations
\cite{recipes88,WASSERMAN95}. Second order means that these methods make use
of the second derivatives of the goal function, while first-order techniques
like standard backpropagation only use the first derivatives. A second order
technique generally finds a better way to a (local) minimum than a first order
technique, but {\bf at a higher computational cost}.

Like standard backpropagation, CGMs iteratively try to get closer to the
minimum. But while standard backpropagation always proceeds down the gradient
of the error function, a conjugate gradient method will proceed in a direction
which is {\bf conjugate} to the directions of the previous steps. Thus the
minimization performed in one step is not partially undone by the next, as it
is the case with standard backpropagation and other gradient descent methods.

%CGMs assume that the goal function is quadratic. If the function is
%approximatively quadratic in the neighbourhood of the minimum, CGMs will
%perform well in this region; otherwise the results are less predictable.


\subsection{Main features of SCG}

Let $w_i$ be a vector from the  space $R^N$, where $N$ is the sum of
the number of weights and of the number of biases of the network. Let $E$ be
the error function we want to minimize.

SCG differs from other CGMs in two points:
\begin{itemize}
\item each iteration $k$ of a CGM computes $w_{k+1}=w_k+\alpha_k \cdot p_k$,
  where $p_k$ is a new conjugate direction, and $\alpha_k$ is the size of the
  step in this direction. Actually $\alpha_k$ is a function of $E''(w_k)$, the
  Hessian matrix of the error function, namely the matrix of the second
  derivatives. In contrast to other CGMs which avoid the complex
  computation of the Hessian and approximate $\alpha_k$ with
  a {\bf time-consuming} line search procedure, SCG makes the following simple
  approximation of the term $s_k$, a key component of the computation of
  $\alpha_k$: 
$$s_k=E''(w_k)\cdot p_k \approx \frac{E'(w_k + \sigma_k\cdot p_k) -
  E'(w_k)}{\sigma_k},\ 0 < \sigma_k \ll 1$$

\item as the Hessian is not always positive definite, which prevents the
  algorithm from achieving good performance, SCG uses a scalar $\lambda_k$
  which is supposed to regulate the indefiniteness of the Hessian. This is a
  kind of Levenberg-Marquardt method \cite{recipes88}, and is
  done by setting: 
$$s_k=\frac{E'(w_k + \sigma_k\cdot p_k) -  E'(w_k)}{\sigma_k} 
+ \lambda_k\cdot p_k$$ and adjusting $\lambda_k$ at each iteration. This is
the main contribution of SCG to both fields of neural learning and
optimization theory. 
\end{itemize}


SCG has been shown to be considerably faster than standard backpropagation and
than other CGMs \cite{MOLLER93}.

\subsection{Parameters of SCG}

As $\sigma_k$ and  $\lambda_k$ are computed from their respective values at
step $k-1$,  SCG has two parameters, namely the initial values $\sigma_1$ and
$\lambda_1$. Their values are not critical but should respect the conditions
$0<\sigma_1\leq 10^{-4}$ and $0<\lambda_1\leq 10^{-6}$. Empirically M{\o}ller
has shown that bigger values of $\sigma_1$ can lead to a slower convergence.

The third parameter is the usual quantity $\Delta_{max}$ (cf.\ standard
backpropagation).

In SNNS, it is usually the responsibility of the user to determine
when the learning process should stop. Unfortunately, the $\lambda_k$
adaptation mechanism sometimes assigns too large values to $\lambda_k$
when no more progress is possible. In order to avoid floating-point
exceptions, we have added a termination criterion\footnote{As it is
  not rare that SCG can not reduce the error during a few consecutive
  epochs, this criterion is computed only when $E(w_{k+1}) \leq
  E(w_k)$.  Without such a precaution, this criterion would stop SCG
  too early.} to SCG.  The criterion is taken from the CGMs presented
in \cite{recipes88}: stop when $$2\cdot (|E(w_{k+1}) - E(w_k)|) \leq
\epsilon_1 \cdot (|E(w_{k+1})| + |E(w_k)|+\epsilon_2)$$ $\epsilon_2$
is a small number used to rectify the special case of converging to a
function value of exactly zero.  It is set to $10^{-10}$.
$\epsilon_1$ is a tolerance depending of the floating-point precision
$\Phi$ of your machine, and it should be set to $\Phi$, which is
usually equal to $10^{-8}$ (simple precision) or to $10^{-16}$ (double
precision). 

To summarize, there are four non-critical parameters:
\begin{enumerate}
\item $\sigma_1$. Should satisfy $0<\sigma_1\leq 10^{-4}$. If 0, will
  be set to $10^{-4}$;
\item $\lambda_1$. Should satisfy $0<\lambda_1\leq 10^{-6}$. If 0,
  will be set to $10^{-6}$;
\item $\Delta_{max}$. See standard backpropagation. Can be set to 0 if
  you don't know what to do with it;
\item $\epsilon_1$. Depends on the floating-point precision. Should be set to
  $10^{-8}$ (simple precision) or to $10^{-16}$ (double precision). If
  0, will be set to $10^{-8}$.
\end{enumerate}

{\bf Note:} SCG is a batch learning method, so shuffling the
patterns has no effect.

\subsection{Complexity of SCG}
The number of epochs is not relevant when comparing SCG to other algorithms
like standard backpropagation. Indeed one iteration in SCG needs the
computation of two gradients, and one call to the error function, while one
iteration in standard backpropagation needs the computation of one gradient
and one call to the error function. M{\o}ller defines a {\em complexity unit}
(cu) to be equivalent to the complexity of one forward passing of all patterns
in the training set. Then computing the error costs 1 cu while computing the
gradient can be estimated to cost 3 cu. According to M{\o}ller's metric, one
iteration of SCG is as complex as around $7/4$ iterations of standard
backpropagation.

{\bf Note:} As the SNNS implementation of SCG is not very well
optimized, the CPU time is not necessarily a good comparison
criterion.

