\documentclass[12pt]{article}
\usepackage{pst-node,pstricks}
\usepackage{colortbl}
\usepackage{color}
\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{algorithm}
\usepackage{pagesize}
\usepackage{times}

\pagesize{paper=a4,width=6in,height=9.5in}

\begin{document}

\setlength{\baselineskip}{1.0cm}

\begin{center}
\begin{Large}
\textbf{A Global Optimization Approach to \\
Neural Network Training} \\
\end{Large}
\vskip 0.5cm
\textbf{C.~Voglis \& I.E.~Lagaris} \\
\textbf{Dept. of Computer Science, University of Ioannina} \\
\textbf{\{voglis, lagaris\}@cs.uoi.gr}
\end{center}
\vskip 0.3cm

\noindent {\bf Abstract}\\ We study effective approaches for
training artificial neural networks (ANN). We argue that local
optimization methods by themselves are not suited for that task.
In fact we show that global optimization methods are absolutely
necessary if the training is required to be robust. This is so
because the objective function under consideration possesses a
multitude of minima while only a few may correspond to acceptable
solutions
that generalize well. \\
\noindent {\bf Keywords}- Artificial neural networks, global
optimization, multistart.

%\section{Introduction}
\vskip 0.5cm \begin{center}{\bf 1. INTRODUCTION} \end{center}
\vskip 0.1cm

\noindent The minimization of multimodal functions with numerous
local and global minima is a problem that frequently arises in
many scientific applications. In general the nature of some
applications is such that it is necessary to detect all the global
minimizers (e.g. \textit{computation of Nash equilibria~[9]} in
game theory) or a set of minima with objective function value in a
specific range (\emph{ energy values in the molecular conformation
problem}~[6]). Another interesting application that requires the
computation of more than one global minimizer is the computation
of \textit{periodic orbits of nonlinear mappings}~[8]. Neural
network training is a problem of similar nature; i.e. the relevant
objective function possesses a multitude of local (and possibly
global) minima.

Consider the classical data fitting problem: \emph {Given $M$
points and associated values $(x_i, y_i),\ i=1, 2, \ldots, M$,
with $x_i \in R^d, \ y_i \in R$, draw a smooth hypersurface that
is optimal in the least square sense}.

The traditional way of solving such problems is to assume a
parametric model (e.g. an Artificial Neural Network) $N(x; p)$ and
adjust the parameters $p$, so as to minimize the deviations, i.e.
minimize the ``Error'':
\begin{equation}
E(p) = \sum_{i=1}^{M}[N(x_i; p) - y_i]^2 \label{FUNC}
\end{equation}

\noindent Thus the problem of training an ANN is transformed into
an optimization one
\begin{eqnarray}
& & \min_{p} E(p) \\
& & s.t.\ \  p \in S \subset R^n \nonumber \label{PROB}
\end{eqnarray}

\noindent Unfortunately the terrain modelled by the error function
can be extremely rugged and often  has a multitude of  local
minima. Obviously, a method that can not escape from local minima
has hardly any chance to find a solution to the problem. We must
add that smaller neural networks generalize better, since they
avoid over-fitting and this is the reason they are preferred for
both classification and regression tasks. On the other hand,
training smaller networks is more difficult  since the error
surface is heavily rugged and there exist only a few good
solutions.

% \section{Multistart-like family in Global Optimization}
\vskip 0.7cm \begin{center}{\bf 2. MULTISTART BASED ALGORITHM IN
GLOBAL OPTIMIZATION} \end{center} \vskip 0.1cm

\noindent It is important to describe in brief the basic framework
of a multistart based global optimization method. In Multistart, a
point is sampled uniformly from the feasible region, and
subsequently a local search is started from it. The weakness of
this algorithm is that the same local minima may be found over and
over again, wasting so computational resources.

The {\bf ``region of attraction''} of a local minimum associated
with a deterministic local search procedure $\mathcal{L}$ is
defined as:
\begin{equation}
A_i \equiv \{x \in S, \mathcal{L}(x)=x^*_i\}
\end{equation}
where $\mathcal{L}(x)$ is the minimizer returned when the local
search procedure $\mathcal{L}$ is started at point $x$.

\begin{algorithm}[!h]
\begin{normalsize}
\begin{description}
\item[Initialize:] Set k=1 \\
\hbox{\ \ \ \ \ \ \ } Sample $x \in S $\\
\hbox{\ \ \ \ \ \ \ } $y_k = \mathcal{L}(x)$ \item[Termination
Control:] If a stopping rule applies STOP. \item[Sample:]  Sample
$x \in S $
\item[Main step:] If ($x \notin \cup_{i=1}^k A_i$) Then \\
\hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } $ y = \mathcal{L}(x) $ \\
\hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } $ k = k + 1 $ \\
\hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } $ y_k = y $ \\
\hbox{\ \ \ \ \ \ \ \ \ } Endif \item[Iterate:] Go back to the
Termination Control step.
\end{description}
\end{normalsize}
\caption{Multistart framework}
\end{algorithm}

\noindent  The algorithm described above, returns a set $Y = \{y_k
\}$ of the recovered local minima. A lot of research is carried
out on  reducing the number of times, the local search procedure
is applied in a way that minimizes the risk of missing a local
minimum.

% \section{Locating Minima in Neural Network Training}

\vskip 0.7cm \begin{center}{\bf 3. LOCATING MINIMA IN NEURAL
NETWORK TRAINING} \end{center} \vskip 0.1cm

\noindent The main purpose of this work is to demonstrate the need
of a multistart based global optimization method for training NNs.
In the literature so far we can distinguish three major classes of
methods:
\begin{itemize}
 \item Local optimization procedures: All methods that attempt
to find a local minimum of the {\emph error function} $E(p)$.
(Gradient descent, conjugate gradient, quasi-Newton methods,
Levenberg-Marquardt)

\item Global optimization procedures (single global minimum):
These  methods employ probabilistic or deterministic strategies,
to overcome local minima and locate a single global optimum.
(Trajectory methods~[1], covering methods[11], evolutionary
algorithms~[10,11], simulated annealing~[4,11])

\item Global optimization procedures (all global minima): These
methods use global strategies to locate all the existing global
minima. (Interval methods~[12], Particle swarm~[2, 3])
\end{itemize}

In this section we are going to present real cases in neural
network training that the above mentioned procedures will not
perform optimally. Note that:
\begin{itemize}
\item Local minima are often poor solutions to the training
problem. Thus, local optimization methods are out of question.
\item The various global minima present different interpolation
behavior, i.e they do not generalize in a similar way.
 \item There are cases where some local minima generalize better than
a global minimum.
\end{itemize}

\noindent We list the two regression problems used to illustrate
our points.

\begin{description}
 \item[Problem A:]We used $40$ evenly distributed points in $[0, 20]$ and their corresponding
function values, to construct the training data set $\mathcal{D}_A
= (x_i, f(x_i)),\ i=1,\ldots,40$ and $500$ points for the test set
$\mathcal{T}_A$, with $f(x) = x \sin(x)$
 \item[Problem B:] We used $40$ evenly distributed points in $[0,
10]$ and their corresponding function values, to construct the
training data set $\mathcal{D}_B = (x_i, f(x_i)),\ i=1,\ldots,40$
and $500$ points for the test set $\mathcal{T}_B$, with $f(x) = x
\sin(x^2)$.
\end{description}

\vskip 0.5cm  \noindent {\bf 3.1 Quality of local minima} \vskip
0.2cm

\noindent Consider a feedforward artificial neural network, with
sigmoid activation functions in the hidden layer. This  model can
be written as:
\begin{eqnarray}
& & N(x;p) = \sum_{i=1}^{n_{h}} p_{3i-2}\sigma(p_{3i-1}x + p_{3i}) \\
& & \textrm{ with } \sigma(z) = \frac{1}{1+e^{-z}} \nonumber
\end{eqnarray}
\noindent where the weight parameters $p$ are numbered as shown in
Figure~\ref{NNET}.


\begin{figure}[!ht]
\centering
\begin{psmatrix}[colsep=1.0cm, rowsep=1.5cm]
 & &  & \circlenode{ou}{$\sigma$}&   \\
 & \circlenode{n1}{$\sigma_1$} &\circlenode{n2}{$\sigma_1$} & $\ldots$ & $\ldots$   & \circlenode{nn}{$\sigma_h$} \\
 & & \circlenode{inb}{$1$} &  & \circlenode{in}{$x$}&
 \psset{linestyle=solid}
 \ncline{->}{n1}{ou}^{$p_1$}
 \ncline{->}{n2}{ou}>{$p_4$}
 \ncline{->}{nn}{ou}^{$p_{3i-2}$}

 \ncline{->}{in}{n1}
 \rput(-5.7, 2.3){$p_2$}
 \ncline{->}{in}{n2}
 \rput(-4.0, 2.0){$p_5$}
 \ncline{->}{in}{nn}
 \rput(-0.5, 1.0){$p_{3i-1}$}
 \ncline{->}{x}{in}
 \ncline{->}{ou}{y}

 \ncline{->}{inb}{n1}
 \rput(-5.7, 0.8){$p_3$}
 \ncline{->}{inb}{n2}
  \rput(-5.1, 0.8){$p_6$}
 \ncline{->}{inb}{nn}
 \rput(-4.0, 0.8){$p_{3i}$}
\end{psmatrix}
\caption{Neural network: Labelling of parameters}\label{NNET}
\end{figure}

One  easily realizes that problem (2) may be solved with a large
number of different values for the parameters.

In order to evaluate the quality of local minima for problem A, we
optimized the error function using a multistart-based global
optimization method~[7]. Our goal was to find as many local minima
as possible. Using six nodes in the hidden layer ($n_h = 6$), we
found more than $10,000$ minima. In Table~1 we present only a
small subset of $20$ minima.

\begin{table}[!h]
\centering \noindent {\tiny
\begin{tabular}{|p{0.5cm}|l|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline
 & Min. & p1 & p2 & p3 & p4 & p5 & p6 & p7 & p8 & p9 & p10 & p11 & p12 \\
\hline \rowcolor{yellow}
1 & 11.93 & -626.79 & 0.49 & -4.05 & 400. & -0.85 & 6.11 & 439.16 & -0.97 & 15.27 & 526.32 & 0.26 & -3.36 \\
\hline
2 & 13.13 & -595.56 & -0.26 & 3.53 & 400. & 1.00 & -15.79 & 504.03 & 0.82 & -5.98 & 276.26 & -0.56 & 4.46 \\
\hline
3 & 59.37 & -730.46 & -0.54 & 6.04 & 400. & 0.87 & -8.98 & 568.78 & 0.96 & -18.08 & 501.58 & -0.28 & 4.46 \\
\hline
4 & 60.26 & -229.63 & 0.89 & -13.88 & 99.48 & 0.37 & -1.81 & 0.00 & 1.03 & -10.39 & 756.47 & 0.24 & -3.36 \\
\hline
5 & 62.42 & -429.90 & -0.42 & 8.15 & 400. & -1.77 & 12.18 & 193.51 & 1.07 & -13.74 & 298.31 & -0.41 & 6.14 \\
\hline
6 & 64.22 & -613.04 & 0.28 & -4.57 & 400. & -1.02 & 19.17 & 433.43 & -0.99 & 10.17 & 296.87 & 0.55 & -6.20 \\
\hline
7 & 70.87 & -373.12 & -0.43 & 8.59 & 400. & 1.94 & -13.30 & 125.49 & 1.11 & -14.25 & 222.39 & -0.42 & 6.22 \\
\hline \rowcolor{yellow}
8 & 80.20 & -577.92 & -0.57 & 6.44 & 400. & -0.94 & 17.86 & 406.32 & -1.01 & 10.42 & 303.61 & -0.34 & 4.89 \\
\hline
9 & 80.31 & -286.48 & -0.28 & 4.87 & 400. & -1.25 & 20.00 & 0.00 & 1.29 & -9.11 & 58.09 & -0.78 & 6.04 \\
\hline
10 & 84.20 & -628.36 & -0.29 & 4.69 & 400. & 0.90 & -14.27 & 305.83 & -1.30 & 13.07 & 513.88 & -0.09 & 2.53 \\
\hline
11 & 84.23 & -630.99 & -0.29 & 4.72 & 400. & 0.90 & -14.21 & 153.35 & 1.30 & -13.06 & 750.10 & -0.09 & 2.65 \\
\hline
12 & 85.34 & -585.91 & 0.06 & -1.95 & 400. & 0.98 & -15.53 & 255.16 & -1.37 & 13.72 & 478.08 & 0.27 & -4.38 \\
\hline
13 & 86.38 & -188.04 & 0.98 & -15.44 & 0.00 & 0.08 & -0.50 & 257.18 & -1.37 & 13.74 & 386.63 & 0.29 & -4.60 \\
\hline
14 & 291.60 & -240.72 & 0.10 & -4.30 & 0.00 & 0.65 & -7.33 & 0.00 & 1.08 & -16.88 & 800.00 & 0.43 & -6.11 \\
\hline
15 & 334.71 & -272.36 & -0.25 & 5.96 & 400. & 1.38 & -18.17 & 142.09 & -0.60 & 8.59 & 0.00 & 0.25 & -5.96 \\
\hline
16 & 353.93 & -270.56 & 0.63 & -9.05 & 400. & 1.36 & -18.06 & 202.06 & 0.32 & -6.61 & 324.18 & -19.58 & -20.00 \\
\hline \rowcolor{yellow}
17 & 353.93 & -270.56 & 0.63 & -9.05 & 400. & 1.36 & -18.06 & 200.80 & -9.01 & -20.00 & 1.26 & 0.32 & -6.61 \\
\hline
18 & 354.72 & -253.81 & -4.02 & -6.56 & 2.04 & 0.63 & -7.44 & 0.00 & 1.10 & -17.15 & 800.00 & 0.49 & -7.00 \\
\hline
19 & 354.85 & -251.78 & 0.63 & -7.45 & 0.00 & -4.27 & -19.58 & 0.00 & 1.10 & -17.15 & 800.00 & 0.49 & -7.01 \\
\hline \rowcolor{yellow}
20 & 828.76 & -580.81 & -18.01& -20 & 101.91  & 1.19 & -20 & -332.60 &  1.24 & -20 & 800 &  1.02 & -17.15 \\
\hline
\end{tabular}
} \caption{A set of $20$ selected local minima (Problem A)}
 \end{table}

We have  sorted these solutions in ascending order of the $E(p)$
value. Intuitively we can assume that the quality of the
approximation is inversely proportional to the Error Function
value achieved for each minimum. This is shown in the
Figure~\ref{Q1}, where we plot $4$ found solutions. Notice that
only the first set of parameters (Solution 1) managed to
approximate the target function accurately.

Consequently the probability that a local search method recovers
such a solution, is rather small considering the large number of
existing local minima.

\begin{figure}[!h] \centering \subfigure[Solution
1]{\includegraphics[scale=0.23]{fit1}}
\subfigure[Solution 8]{\includegraphics[scale=0.23]{fit2}} \\
\subfigure[Solution 17]{\includegraphics[scale=0.23]{fit3}}
\subfigure[Solution 20]{\includegraphics[scale=0.23]{fit4}}
\caption{Quality of local minima found.} \label{Q1}
\end{figure}

\vskip 0.5cm  \noindent {\bf 3.2 Quality of the global minima}
\vskip 0.2cm

\noindent In the past, many researchers used global optimization
algorithms to search for a single global minimum. Such strategies
perform better than local techniques, however they do not take in
account the existence of many {\it global} minima. If this is the
case (which is quite common), multistart based global optimization
algorithms, that recover all the global minima of the problem can
be used to identify (by means of a test set) the best parameter
values.

\begin{table}
\centering
\begin{normalsize}
\begin{tabular}{|l|c|c|c|}
\hline
$j$ &  Train Error  & Test Error & $||\vec{p}_1 - \vec{p}_j||_2$\\
\hline 1 & 0.0013 & 4.38 & 0.0 \\
\hline 2 & 0.0012 & 0.28 & 6246.69 \\
\hline
3 & 0.0014 & 4.0 &7017.74 \\
\hline 4 \phantom{0}& 0.0016 & 0.1 & 6162.54\\
\hline
\end{tabular}
\end{normalsize}\
\caption{An example of 4 global minima }
\end{table}


To illustrate this we solved Problem B, using a neural network
with $15$ nodes in the hidden layer. Four global minima were
recovered, presented in Table~2. Equivalent solutions generated by
node-permutation were excluded. As can be realized by inspecting
Table~2, the four solutions perform quite differently in the test
set, yielding a clear winner (Solution \#4, with test error
$0.1$). In Figure~\ref{ACCURACY} we plot for each point in the
test set, the accuracy of the approximation, i.e. the quantity
$|f(x_i) - N(x_i;p)|$.

\begin{figure}[!ht] \centering \subfigure[Solution
1 - Accuracy]{\includegraphics[angle=-90,scale=0.23]{figura1}}
\subfigure[Solution 2 - Accuracy]{\includegraphics[angle=-90,scale=0.23]{figura2}} \\
\subfigure[Solution 3 -
Accuracy]{\includegraphics[angle=-90,scale=0.23]{figura3}}
\subfigure[Solution 4 -
Accuracy]{\includegraphics[angle=-90,scale=0.23]{figura4}}
\caption{Quality of local minima found.} \label{ACCURACY}
\end{figure}

\vskip 0.5cm  \noindent {\bf 3.3 Finding Multiple Minima vs.
Overtraining} \vskip 0.2cm

\noindent Overtraining is a frequently encountered problem in NN
training. This happens when the model parameters are extremely
well tuned to the training data and interpolate inaccurately in
nearby points.

Such kind of solutions may correspond to global minima as well. So
it is important to maintain as candidate solutions global and
local minima as well.

To illustrate the above, we solved Problem~A, using TML and a
neural network consisting of $10$ hidden nodes. In
Table~\ref{TAB3} we present the four best solutions found. It is
remarkable that the solution with the lowest error in the training
set displays the worst error in the test set. The first two
solutions are shown in Figure~\ref{OVER}. Notice the large
oscillation near zero, a characteristic sign of overtraining.

\begin{table}
\centering
\begin{normalsize}
\begin{tabular}{|l|c|c|c|}
\hline
&  Train Error & Test Error & $||p_1 - p_j||_2$\\
\hline 1 & 1.10E-4 & 1.7E+5 & 0.0\\
\hline 2 \phantom{0}& 3.02E-2 & 0.78 &  3914.18\\
\hline
3 & 7.9E-2  & 0.89 & 3937.74 \\
\hline 4 & 0.22& 2.13 & 1167.21 \\
\hline
\end{tabular}
\end{normalsize}\
\caption{An example of overtraining. } \label{TAB3}
\end{table}

\begin{figure}[!ht] \centering \subfigure[Solution
1. Overtrained solution - Error in test set = 169953. Note the
behavior around
$x=0$]{\includegraphics[angle=-90,scale=0.25]{fig1}}
\subfigure[Solution 2. Quality  solution - Error in test set = 0.78]{\includegraphics[angle=-90,scale=0.25]{fig2}} \\
\caption{An example of overtraining.}\label{OVER}
\end{figure}


\vskip 0.7cm \begin{center}{\bf 4. CONCLUSIONS} \end{center}
\vskip 0.1cm

\noindent The plethora of local minima inherent in the objective
function that results in the case of neural network training,
renders necessary the use of global optimization methods. Since
generalization is a very important property that can be verified
only a-posteriori (i.e. by using a test data set),
multistart-based methods that recover all the local (and global
minima) should be preferred.

In this article we presented a framework that can be used for
achieving robust neural network training. Almost any
multistart-based method may be used since most variations aim in
collecting all the local minima inside the feasible region.

The test problems presented here are constructed for illustration
purposes, however they are typical and represent the difficulties
of real world problems.


\vskip 0.7cm \begin{center}{\bf REFERENCES} \end{center}
\vspace{-0.7cm}
\begin{small}
\begin{enumerate}
\item  Shang,~Y. \& Wah,~B.~W.~(1996). Global optimization for
neural network training, {\it IEEE Computer}, v.~ 29, no.~3,
pp.~45--54. \vspace{-0.3cm}
 \item   Parsopoulos,~K.~.E~\& Vrahatis,~M.~N.,
(2004). On the computation of all global minimizers through
particle swarm optimization, {\it IEEE Transactions on
Evolutionary Computation}, v.~8, no.~3, pp.~211--224.
\vspace{-0.3cm}
 \item Plagiannakos,~V.~P., Magoulas,~G.~D., Androulakis,~G.~S., \&
Vrahatis,~M.~N. (1999). Global search methods for neural network
training,  {\it Proceedings of the 3rd IEEE-IMACS World
Multiconference on Circuits, Systems, Communications and
Computers}, vol.~1, pp.~3651--3656.
 \vspace{-0.7cm}
 \item  Corana,~A., Marchesi,~M., Martini,~C., \& Ridella,~S. (1987). Minimizing
multimodal functions of continuous variables with the Simulated
Annealing algorithm, {\it ACM Trans. Math. Soft.}, vol.~13,
pp.~262--280.  \vspace{-0.3cm}
 \item  Gori,~M. \& Tesi,~A. (1992). On the problem
of local minima in backpropagation, {\it IEEE Trans. Patterns
Analysis and Machine Intelligence}, vol.~14, pp.~76--85.
\vspace{-0.3cm}

\item  Saunders,~M., Houk,~K.~N., Wu,~Yun-Dong., Still,~W.~C.,
Lipton,~M., Chang,~W.~G. (1990). Conformations of
Cycloheptadecane. A comparison of methods for conformational
searching, {\it J.~Am.~Chem.~Soc.}, vol.~112, pp.~1419--1427.
\vspace{-0.3cm}

\item Lagaris,~I.~E., Papageorgiou,~D.~G., \& Theos,~F.~V. (2004).
PANMIN: Sequential and parallel global optimization procedures
with a variety of options for the local search strategy,  {\it
Computer Physics Communications}, vol.~159, pp.~63-69.
 \vspace{-0.3cm}

 \item Vrahatis,~M.~N. (1995) An efficient method for locating and
 computing periodic orbits, {\it J. Comp. Phys.}, vol. 119, pp.
 105--119.
 \vspace{-0.3cm}

\item Floudas,~C. et.~al. (1999)  Handbook of Test Problems in
Local and Global Optimization. Dordrecht: Kluwer Academic
Publishers.
 \vspace{-0.3cm}
\item Goldberg, D. E. (1989). Genetic Algorithms in Search,
Optimization, and Machine Learning. Addison-Wesley: Reading, MA.

 \vspace{-0.3cm}
\item Torn,~A. \& Zilinskas,~A. (1987). Global optimization.
Springer--Verlang.
 \vspace{-0.3cm}

\item Hansen,~E. (1992) Global Optimization Using Interval
Analysis. New York:Dekker.

\end{enumerate}
\end{small}

\end{document}
