% Document Type: LaTeX
% Master File: UserManual.tex
% 
% Date: %G
% File: %W


\documentstyle[a4,11pt,parskip,epsf,twoside,epic,eepic]{report}

\makeindex

\pagestyle{headings}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% MACRO \screendump
% =================
\newcommand{\screendump}[2]{%
  \begingroup                % keep redefinition of \epsfsize local
    \def\epsfsize##1##2{#1##1}% scale to #1% of natural size
    \epsfbox{#2}%            % read image
  \endgroup
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% MARGIN - Values
% ===============
\evensidemargin0cm
\oddsidemargin0.6cm
\setlength{\textwidth}{15cm}
%\sloppy
    

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% COUNTER - VALUES
% =================
\setcounter{secnumdepth}{3}
\setcounter{tocdepth}{3}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% INCLUDE - Files:
% ================
% enter files that should be compiled by LaTeX seperated by comma.
% (useful while editing just one chapter, leaving all
% other files untouched)
%\includeonly{kernel_implem}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% D O C U M E N T
% ===============
\begin{document}

\bibliographystyle{alpha}
\nocite{Fahlma88,FahLeb91}

\include{title_ext}

\clearpage
\pagenumbering{roman}

\renewcommand{\baselinestretch}{0.6}\small\normalsize
\tableofcontents
%\thispagestyle{empty}
\renewcommand{\baselinestretch}{1.0}\small\normalsize

\clearpage
\pagenumbering{arabic}

% \part{Introduction}

\chapter{The Purpose of this Document}

There are roughly two new releases of SNNS every year. At this pace it
is clear that the changes from version to version are not fundamental
and that the corresponding changes and additions in the documentation
affect only a few pages of the manual.

In order to save a few trees it may be advisable to not print out all
the documentation, that actually hasn't changed much, again and again.
So we decided to provide a sort of an update document to the manual.
This document is prepared for all those users that already have an
older manual and wish to receive only an update for the new
functionality.

We do like to point out, however, that this document can only contain
those parts that are entirely new. All those little improvements,
cross references, and additions in chapters that are mainly unchanged
can not be included here. So we encourage the users either to use the
complete manual online or at least to print out every other release of
the manual in order to become aware of these changes.

Beginners anyways should start with the full documentation and ignore
these excerpts.

\section{New Features of Release 4.1}

Users already familiar with SNNS and its usage may be interested in
the differences between the versions 4.0 and 4.1. New users of SNNS
may skip this section and proceed with the next chapter.

New Features of Release 4.1:

\begin{enumerate}
  
\item New batch execution language batchman

\item Integration of the genetic algorithm tool Enzo.

\item Improved window handling. On re-opening of a SNNS window it gets
  put on top, instead of issuing an error message.

\item new learning algorithm 'scaled conjugated gradient' (SCG)

\item The parameter lists in the control panel adapt to the number of
  paramters required, i.e. all widgets present need to be filled out.

\item WinSNNS, a MS-Windows front-end to SNNS batch execution on unix
  workstations. WinSNNS is NOT part of our official SNNS distribution!
  It can be found at http://www.lans.ece.utexas.edu/winsnns.html.\\
  Please contact ghosh@pine.ece.utexas.edu for more information.

\item optional parameter `Teacher-Forcing' for Jordan networks
  introduced.

\item validation now possible for BPTT networks

\item Extensive debugging:
  \begin{enumerate}

  \item Seg-fault when trying to train a network without output units

  \item Seg-fault when pressing the info button without loaded patterns
  
  \item wrong feedback loops in associative memory nets deleted

  \item wrong activation functions in associative memory when
    constructed with bignet

  \item wrong initialization function in kohonen networks when
    constructed with bignet

  \item Wrong error computation in Hebbian learning

  \item Wrong error computation of analyze function band

  \item Wrong MSE computation for validation

  \item Better font size adaption of label widgets

  \item Pruning now allows validation with 0 cycles

  \item GRAPH panel could sometimes not be closed

  \item Wrong scanning of update parameters in snnsbat

  \item Error in the manual: Missing parameter of BackpropWeightDecay
  \end{enumerate}


\end{enumerate}

\include{batch_version}
\setcounter{chapter}{4}
\setcounter{section}{2}

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


\bibliography{UserManual}

\end{document}


