%% LATEX TWICE TO GET REFERENCES RIGHT
\documentstyle[11pt]{article}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Theorem}
\newtheorem{itlemma}{Lemma}[section] %number by section (set in \em by default)
%%%same numbering counter as itlemmas:
\newtheorem{itproposition}[itlemma]{Proposition}
\newtheorem{itcorollary}[itlemma]{Corollary}
\newtheorem{itremark}[itlemma]{Remark}
\newtheorem{itnote}[itlemma]{Note}
\newtheorem{itdefinition}[itlemma]{Definition}
\newtheorem{itexercise}[itlemma]{Exercise}
\newtheorem{itexample}[itlemma]{Example}

\newenvironment{lemma}{\begin{itlemma}\rm}{\end{itlemma}} %no-italics
\newenvironment{remark}{\begin{itremark}\rm}{\end{itremark}} %no-italics
\newenvironment{corollary}{\begin{itcorollary}\rm}{\end{itcorollary}}
\newenvironment{proposition}{\begin{itproposition}\rm}{\end{itproposition}}
\newenvironment{definition}{\begin{itdefinition}\rm}{\end{itdefinition}}
\newenvironment{exercise}{\begin{itexercise}\rm}{\end{itexercise}}
\newenvironment{example}{\begin{itexample}\rm}{\end{itexample}}

\tolerance=1600 %allow some tolerance in extending after line.
\parskip=3pt plus 1pt minus 1pt
\overfullrule=0pt %no dark lines if overfull

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This are for choices.  They take 4 or 6 args
%% (carriage returns allowed in between}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\twoif}[4]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\end{array}\right.
}
\newcommand{\threeif}[6]{
\left\{ \begin{array}{ll}#1&#2\\#3&#4\\#5&#6\end{array}\right.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\partmlab#1#2#3#4#5#6#7#8{\bordermatrix{&#1&#2\cr#3&#5&#6\cr
					\noalign{\medskip}#4&#7&#8\cr}}
%% For 2by2 partitioned matrices; arguments are: two labels of top, side,
%% 4 entries (row by row).  If entries are themselves matrix or pmatrix,
%% better for readability of source to define first: \def\matrix1{...} etc.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\bigframebox}[1]{\framebox{\parbox{\smallerwidth}{#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Warning: use \noindent before!
% AND IN TEXT, after begin doc, do:
% \newlength{\smallerwidth}  %for bigboxes
% \setlength{\smallerwidth}{\textwidth}
% \addtolength{\smallerwidth}{-8pt} %MUST BE DONE AFTER begin doc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def \beq {\begin{eqnarray}}
\def \eeq {\end{eqnarray}}
\def \beqn {\begin{eqnarray*}}
\def \eeqn {\end{eqnarray*}}

\newcommand{\rf}[1]{[\ref{#1}]} %bibliographical references

\newcommand{\text}[1]{\hbox{\rm \ #1\ \/}}
\newcommand{\be}[1]{\begin{equation}\label{#1}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bl}[1]{\begin{lemma}\label{#1}}
\newcommand{\ble}[1]{\begin{lemmaex}\label{#1}}
\newcommand{\br}[1]{\begin{remark}\label{#1}}
\newcommand{\bn}[1]{\begin{note}\label{#1}}
\newcommand{\bt}[1]{\begin{theorem}\label{#1}}
\newcommand{\bd}[1]{\begin{definition}\label{#1}}
\newcommand{\bp}[1]{\begin{proposition}\label{#1}}
\newcommand{\bc}[1]{\begin{corollary}\label{#1}}
\newcommand{\bfact}[1]{\begin{fact}\label{#1}}
\newcommand{\ber}[1]{\begin{exercise}\label{#1}}
\newcommand{\bex}[1]{\begin{example}\label{#1}}
\newcommand{\bem}[1]{\begin{example}\label{#1}}  %Yes, 2 different ones...
\newcommand{\ec}{\mybox\end{corollary}}
\newcommand{\efact}{\mybox\end{fact}}
\newcommand{\eer}{\mybox\end{exercise}}
\newcommand{\eex}{\mybox\end{example}}
\newcommand{\eem}{\mybox\end{example}}
\newcommand{\el}{\mybox\end{lemma}}
\newcommand{\ele}{\mybox\end{lemmaex}}
\newcommand{\er}{\mybox\end{remark}}
\newcommand{\en}{\mybox\end{note}}
\newcommand{\et}{\qed\end{theorem}}
\newcommand{\ed}{\mybox\end{definition}}
\newcommand{\ep}{\mybox\end{proposition}}
\newcommand{\epr}{\end{proof}}
\newcommand{\bpr}{\begin{proof}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  These are just for statements, no "qed" box is put in.
%%  (Also for when I have to finish something after a displayed equation
%%        or itemized.)
\newcommand{\ecs}{\end{corollary}}
\newcommand{\eers}{\end{exercise}}
\newcommand{\eexs}{\end{example}}
\newcommand{\eems}{\end{example}}
\newcommand{\els}{\end{lemma}}
\newcommand{\eles}{\end{lemmaex}}
\newcommand{\ers}{\end{remark}}
\newcommand{\ens}{\end{note}}
\newcommand{\ets}{\end{theorem}}
\newcommand{\eds}{\end{definition}}
\newcommand{\eps}{\end{proposition}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\qed}{\hfill \halmos} %put \qed at right margin
\newcommand{\mybox}{\hfill $\Box$} %put \qed at right margin (white square)

%\newcommand{\pmat}[2]{\left( \begin{array}{#1} #2 \end{array} \right) }
%%use as e.g. \pmat{cc}{ a&b\\ a &c }  Note 'cc' for 2 Centered cols
%%can also use \pmatrix{ a&b\cr a &c \cr} for plainTeX standard construct
%\setcounter{page}{27} should set the CURRENT page to 27

\def \R {\bb R} % reals
\def \C {\bb C} % complexes
\def \Z {\bb Z} % integers
\def \X {\bb X} % for this paper only!
\def \inter {{\rm int \,}}
\def \rank {{\rm rank \,}}
%\def \inf {{\rm inf \,}}  %better in Latex -- subscripts OK!
%\def \min {{\rm min \,}}
\def \im {{\rm im \,}}
\def \ker {{\rm ker \,}}
\def \norm #1{\Vert #1 \Vert}
\def \ip #1\by #2{\langle #1 , #2 \rangle}
\def \Sone {{\bf S}^1} % circle
\def \wigglearrow {\sim \mkern -6mu >}

\def \today {\ifcase \month \or January\or February\or  
  March\or April\or May\or June\or July\or August\or 
  September\or October\or November\or December\fi\   
  \number \day, \number \year}                       
\newcommand{\comment}[1]{}
\newcommand{\halmos}{\rule{1ex}{1.4ex}}
%alternative to \qed (see below)
\newenvironment{proof}{\noindent {\em Proof}.\ }{\hspace*{\fill}$\halmos$\medskip}

%\def\qed{\kern 1em \vrule height .5em width .5em depth 0em}
%(I now use new qed: in right margin)

\def\vbar{\mathchoice{\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height4.1ptdepth-.35ptwidth.6pt\kern-.6pt}
   {\vrule height3.1ptdepth-.25ptwidth.5pt\kern-.5pt}}
\def\fudge{\mathchoice{}{}{\mkern.5mu}{\mkern.8mu}}
\def\bbc#1#2{{\rm \mkern#2mu\vbar\mkern-#2mu#1}}
\def\bbb#1{{\rm I\mkern-3.5mu #1}}
\def\bba#1#2{{\rm #1\mkern-#2mu\fudge #1}}
\def\bb#1{{\count4=`#1 \advance\count4by-64 \ifcase\count4\or\bba A{11.5}\or
   \bbb B\or\bbc C{5}\or\bbb D\or\bbb E\or\bbb F \or\bbc G{5}\or\bbb H\or
   \bbb I\or\bbc J{3}\or\bbb K\or\bbb L \or\bbb M\or\bbb N\or\bbc O{5} \or
   \bbb P\or\bbc Q{5}\or\bbb R\or\bbc S{4.2}\or\bba T{10.5}\or\bbc U{5}\or
%   \bbb P\or\bbc Q{5}\or\bbb R\or\bba S{8}\or\bba T{10.5}\or\bbc U{5}\or
   \bba V{12}\or\bba W{16.5}\or\bba X{11}\or\bba Y{11.7}\or\bba Z{7.5}\fi}}
%
%
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%% read as: theFOOTNOTE (i.e. the command  executed when doing a footnote) is
%% now to be set as a FOOTNOTESYMBOL (type of number) value of counter
%% FOOTNOTE (Instead of roman).  See LaTeX manual pp.91-92 as well as 175.
\def\bi{\begin{itemize}}
\def\ei{\end{itemize}}
\def\ben{\begin{enumerate}}
\def\een{\end{enumerate}}
\def\st{\, | \,}

\newcommand{\myboxineq}{\eqno\Box} %put \qed at margin (white square) in eqn
\newcommand{\qedineq}{\eqno\halmos} %put \qed at margin in eqn

\topmargin -0.5in %default is 0.0, i.e. 1 inch from top.  Now it is 0.5
\textheight 9in
\oddsidemargin 0.25in %more reasonable margins!  (This is 1.25; can use <0 too)
\evensidemargin 0.25in %(same as above)
\textwidth 6.25in %(could use also -.5,-.5,7.5 for instance)
\tolerance=1600 %allow some tolerance in extending after line.
\parskip=3pt plus 1pt minus 1pt
\overfullrule=0pt %no dark lines if overfull

%%%% FROM HERE, macros special for paper
\def\mm{m}
\def\pp{p}
\def\proj{\pi _1} % projection on first group of coordinates
\def\x{u}  % vector argument
\def\SEC{(SEC)}
\def\SECo{(SEC$^0$)}
\def\INV{(INV)}
\def\Fp{{\cal F}_\pp}
\def\Fpm{{\cal F}_\pp^\mm}  %there is a 3,3 and a 2,1 in text

\def\Rm{\R^m}
\def\Rn{\R^n}
\newcommand{\ball}[2]{{\bb B}(#1,#2)}
\newcommand{\cball}[2]{\overline {\bb B} (#1,#2)}
\def\Fnm{{\cal F}_n^\mm}
\def\clos{{\rm clos\,}}
\def\inter{{\rm int\,}}

\def\CCF{compatible class of functions}
\begin{document}

\pagestyle{empty}
\begin{flushright}
{\sl Draft-\today}
\end{flushright}
\vfill
\begin{center} 
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{.25cm}
{\bf 
Reducibility and Equivalence of Polygonal Feedforward Neural Networks
with respect to the sigmoidal type feedforward nets
}
\vspace{.25cm}
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{1cm}

Saleh Elmohammed\\
C. K. Mohan\\
School of Computer Science,
S.U,\\
Syracuse, NY 13244\\
E-mails: saleh@top.cis.syr.edu , \, mohan@top.cis.syr.edu\\
\end{center}

\vspace{1.5cm}
\centerline{ABSTRACT}

We exhibit how Sussmann's network reducibility and equivalence conditions 
can be adopted to feedforward structures composed of piecewise linear activation functions.
In the second part of the paper we investigate the possibility of
applying these two conditions to Maass's $\gamma$-circuits.


\vfill
\noindent{\bf Key words : Neural nets, piecewise linear functions, 
sigmoidal functions, $\gamma$-gates, clipping functions, 
linear functions, threshold functions, reducible and irreducible nets}

\vfill
\centerline{\today}
\vfill

\newpage

\pagestyle{plain}

\section{Some Background}

Sussmann \cite{Sussmann-91} examines network reducibility and equivalence w.r.t 
the input-output mappings involved. The net structures considered by \cite{Sussmann-91} are feedforward
with single hidden layer nodes each carrying a hyperbolic tangent activation
function. The units of the output layer adopt the same sort of transfer
function. The investigation of this paper will draw on work
\cite{Sussmann-91} as well as that of Maass et al.\cite{Maass-91} and \cite{Chester-91-draft}.
The work of Maass et al.\cite{Maass-91} examines to  some extent the complexity
of boolean circuits {\it BCs} and shows the capability of $\gamma$-circuits to 
approximate {\it BCs}. Other relevant work is that which investigates 
the complexities of feedforward nets carrying linear, quadratic, threshold, 
or nonlinear (i.e. sigmoidal) node functions.

\subsection{Piecewise Linear Nets}

\subsubsection{Why are we interested in them?}

Chester \cite{Chester-91}, in his dimacs-91 presentation, have presented some
of the generalization capabilities of what is called {\it piecewise linear nets} ($PLN$).
The major reasons we know of behind using them are:
{\it First}, piecewise linear functions ($PLF$) are simpler than other functions 
(including the sigmoids). 

{\it Second}, the sigmoidal functions were introduced as smooth versions of certain piecewise
linear transfer functions (i.e. the clipping type). Third, $PLF$ are often used to
approximate sigmoidal functions in some of those fast computer implementations of
feedforward nets. This approximation goes back to Kolmogorov (see Lorentz 1986) who
proved the result that any continuous function on $[0,1]^d$ can be exactly
approximated as a computation of sums and continuous one dimensional functions.
Lorentz's proof is to construct a PLF $g_i^{(\epsilon)}$ with the property that
for every $x$ in the cube the majority (i.e at least $d+1$) of the values
$g_i^{(\epsilon)}(\sum \, h_{jk}(x))$ (for $j=1,\ldots, 2d+1$) are within 
$\epsilon$ of $f(x)$.

{\it Third}, the clipping functions play a quite useful role as outlined 
recently by Hertz et. al \cite{Hertz-91} (see the section on discretization
and clipping).

{\it Fourth}, it stated in Sontag's work\cite{Sontag3} that the conventional
sigmoid as well as the $PLF$ satisfy the criterion of continuity and differentiablity
(see conditions $S_1$ and $S_2$ of definition 3.2 in \cite{Sontag3}).

\subsubsection{Definitions}

In this section we will attempt to define most of the terms and concepts used 
throughout this investigation.

Polygonal (or piecewise linear) functions are continuous on some given interval
$[a,b]$. A formal definition from Royden's {\it Real Analysis}
can be stated as follow (see \cite{Royden} for more on the question
of function continuity):

\bd{polygonal-func-dfn}
A continuous function $\varphi$ on $[a,b]$ is called {\it polygonal} 
(or {\it piecewise linear}) if there is a subdivision $a = x_0 < x_1 < \ldots < x_n = b$
such that $\varphi$ is linear on each interval $[x_i , x_{i+1}]$. 
So given an arbitrary continuous function $f$ on $[a,b]$ and $\epsilon$ a positive
number, there always a polygonal function $\varphi$ on $[a,b]$ with 
$\mid f(x) - \varphi (x) \mid < \epsilon$ for all $x \in [a,b]$.
\ed

Two types of functions that are considered to fall in the function category of 
(\ref{polygonal-func-dfn}) are the {\it clipping} and the {\it threshold} 
functions \cite{Chester-91-draft}.

\bd{clip-func-dfn}
The {\it clip function} is the function ($c$) of one argument such that:
\be{clip-form-1}
c(x) =
\threeif {0} {\text{if} x  <  0}
         {x} {\text{if} 0 \leq x \leq 1}
         {1} {\text{if} x > 1}
\ee
Another possible form :
\be{clip-form-2}
c(x) =
\threeif {-1} {\text{if} x  <  -1}
         {x} {\text{if} -1 \leq x \leq 1}
         {1} {\text{if} x > 1}
\ee
A third form can be:
\be{clip-form-3}
c(x) =
\threeif {-1} {\text{if} x  <  0}
         {x} {\text{if} 0 \leq x \leq 1}
         {1} {\text{if} x > 1}
\ee
\ed

\bd{threshold-func-dfn}
The {\it threshold function} is the function ($t$) of one argument such that
\be{thresh-form-1}
t(x) =
\twoif {1} {\text{if} x > 0}
       {0} {\text{otherwise}}
\ee
It also takes the following form:
\be{thresh-form-2}
t(x) =
\twoif {0} {\text{if} x \leq 0}
       {1} {\text{if} x > 0}
\ee
In various literature, {\it threshold} functions are called {\it Hardlimiters} or
{\it Heaviside} functions.
\ed

\bd{polygonal-net-dfn}
A polygonal network or $PLN$ is a feedforward multilayer net for which the transfer
functions in the nodes are limited to the clip function ($c$) and the
threshold function ($t$).
\ed

\bl{lemma-1}
If a k-layer $PLN$ has an output value $x^k_i$ such that $0 < x^k_i < 1$, then
the equation for that output value can be written as
$$
x^k_i =
\sum_{j=0}^{n_k} \, w^k_{ij}\, x^{k-1}_j .
$$
\els

\bd{general-dfn}
Let $I_n$ denote the n-dimensional unit cube, $[0,1]^n$. Let the space of continuous
functions on $I_n$ to be $C(I_n)$ and use $\norm{f}$ to denote the supremum (or uniform)
norm of an $f \in C(I_n)$. Now to find out the data interpolation power of the 
network is to determine the conditions under which sums of the form:
$$
G(x) = \sum_{j=1}^N \alpha_j \sigma ({y_j}^T x + \theta_j)
$$
are dense in $C(I_n)$ w.r.t the supremum norm. The form of the above $G$ function is
precisely the form of the output function of an $n \Rightarrow N \Rightarrow 1$ network.
\ed

\bd{hidden-func-dfn}
Given the function $\sigma \;:\; \R \rightarrow \R$. When dealing with feedforward
structures, $\sigma$ is often to be taken as either a {\it sigmoid}
$\sigma (x) = {1 \over 1 + e^{-x}}$ or equivalently, up to translations and change of coordinates,
{\it the hyperbolic tangent} $\sigma(x) = Tanh(x)$. The {\it threshold} function
defined in definition (\ref{threshold-func-dfn})
can be approximated well by $\sigma(\gamma \cdot x)$ when the ``gain''  $\gamma$
is reasonably large.
\ed

\bd{hyperplane-dfn-1}
A {\it hyperplane} in $\R^n$ is a set of points $x = (x_1,\ldots, x_n)$ satisfying
$\sum_{k=1}^n a_k x_k = 0$, where $a_k$ are real numbers and all $a_k$, $k=1, \ldots, n$
are zero.
Under the same assumptions, the set ${cal\ H}$ of points for which $\sum_{k=1}^n a_k x_k \leq a_0$
is called {\it closed half-space}.
\ed

Another possible definition of a {\it hyperplane} is:
\bd{variety-dfn}
A set ${\cal V}$ in the space ${\cal E}^n$ is said to be a {\it linear variety}, if given $x_1$, $x_2$
in ${\cal V}$ we have $\lambda x_1 + (1- \lambda) x_2$ in ${\cal V}$, for all numbers $\lambda$.
\ed

\bd{hyperplane-dfn-2}
A hyperplane in ${\cal E}^n$ is an ($n-1$) dimensional linear variety.
\ed

\bt{Cybenko-89-theorem}
\cite{Cybenko1-89} Let $\sigma$ be a sigmoidal function (as in definition \ref{hidden-func-dfn}).
Then finite sums of the form :
\be{one-layer-func}
G(x) = \sum_{j=1}^N \alpha_j \sigma ({y_j}^T x + \theta_j)
\ee
are dense in $C(I_n)$. In other words, given any function $f \in C(I_n)$ and 
$epsilon > 0$, there is a sum, $G(x)$, of the above form, for which $|G(x) - f(x)| < epsilon$
for all $x \in I_n$.
\ets

\bd{step-func-dfn}
A real-values function ($\varphi$) defined on an interval $[a,b]$ is called {\it step function}
if there is a partition $a = x_0 < x_1 < \ldots < x_n =b$ such that for each ($i$) the
function ($\varphi$) assumes only one value in the interval ($x_i, x_{i+1}$). Note:
a step function ($\varphi$) is lower semi-continuous iff $\varphi (x_i) \leq min{(x_{i-1}, x_i),
(x_i, x_{i+1})}$.
\ed

\subsection{Some comments about general problem transformation}

In areas such as computational geometry \cite{Shamos-88}, problem reducibility or 
transformation can be simply illustrated with the following steps:
Let $P_1$ and $P_2$ are 2 given problems (and also related to each other), and $P_1$ 
can be solved as follows:

(1) The input to $P_1$ is converted into a suitable input to $P_2$.

(2) Problem $P_2$ is solved.

(3) The output of $P_2$ is transformed into a correct solution to $P_1$.

If the above 3 steps are achieved then problem $P_1$ has been transformed to
$P_2$.

On the other hand, our technique of transformation and reducibility
is a bit different from the approach taken in the above 3 steps. 
{\it First}, unlike step (2) above,
we do not know the exact topology or structure of the second net before hand. 
{\it Second}, the original and the derived networks are presented with the same
set of input data. {\it Third}, the output of the derived network is necessarily and
must be similar to the output of the transformed net.

\br{first-remark}
Ordinarly, transformability is not a symmetric relation. When $P_1$ and $P_2$ (in our
case, starting network and target network) are mutually transformable , we say
they are equivalent.
\er

\subsection{Some relevant notes about network complexity}

In a recent work of Indurkhya and Weiss \cite{Wiess-91}, a complexity measure of
feedforward networks has been adapted. In short, given a net with
a single hidden layer, the complexity form of the net can be stated as follows:
\be{net-complexity-form}
C_X = (N_I * N_H) + (N_H * N_O) + N_O + N_H
\ee
Where $ I, H, O$ stand for  input, hidden and output respectively. $N_I , N_H, N_O$ stand for
number of units in the corresponding layers. The process of network reducibility aims at the
reduction of $C_X$. The work of \cite{Weiss-91} addresses the complexity issues in the networks 
of sigmoid units, but we will assume such a measure is applicable to $PLF$ also.


\section{The Background}
H. Sussmann proved what he called the {\it uniqueness theorem} in the framework of 
feedforward nets. It is stated that {\it 2 irreducible feedforward nets with the
same input-output maps are related by a transformation in ${\cal G}$}, where
${\cal G}$ is a discrete symmetry group of nets as originally proposed by Hecht-Nielsen 
\cite{H-Nielson}.

The other major work that will be investigated w.r.t Sussmann's is that outlined in
\cite{Chester-91-draft}. Again, Sussmann's main point is {\it to show that 2 input-output
equivalent nets must necessarily be the same net, up to some simple internal symmetries}.
On the other hand, D. Chester in his recent draft states how a piecewise linear
network can be simplified, reduced and transformed without affecting the I/O mapping
of the net. It is quite clear to us that there are a number of direct and indirect
correspondence between these 2 works regarding network simplification. This 
correspondence is examined in this work.

\section{Brief Synapses of Sussmann and Chester main points}

\subsection{Sussmann reducibility conditions}

Given the net in [Figure 1], as in \cite{Sussmann-91}, we associate ($n$) affine
functions:
\be{aff-func}
 x \in \R^m \longrightarrow v_j (x) \in \R ,\;\;\;\; j=1,\ldots,n.
\ee

\bd{affine-dfn}
If 2 linear affine functions $\alpha$ and $\beta$ on $\R^m$, we have $|\alpha(x)| = |\beta(x)|$
for all $x \in \R^m$ then $\alpha$ and $\beta$ are sign-equivalent.
\ed

The above definition \ref{affine-dfn} means that either 2 neurons compute
the same function or the sum of their outputs is always equal to zero whenever
they are given the same inputs.

A feedforward network ---see Figure 1--- is reducible if one or more of 
the following conditions hold:

(I) One of the $c_j$, for $j =1,\ldots,n,$ vanishes.

(II) There exist 2 different indices $n_1,n_2 \in {1,\ldots,n}$ such that the functionals
$v_{n_1}$ and $v_{n_2}$ are sign-equivalent.

(III) One of the functionals $v_j$ is constant.

Next we examine each of the above 3 cases.

(I') When any one of the connection weights ---see Figure 1--- reduces to zero, the 
corresponding hidden node $v_j$ and its weights $w_{ij}$ (for $i=1, \ldots, n$) are removed 
leading to a reduced net.

(II') Here is a rough sketch of how this condition goes:
Sussmann has assumed that $\sigma(.)$ is an odd function which implies that 
$\sigma(\pm s) \equiv \pm \sigma(s)$. From this, the combined output after removing $n_1$
is $\pm c_{n_1} \sigma(v_{n_2} (x)) + c_{n_2} \sigma(v_{n_2} (x))$ which is
equivalent to:
\be{merge-form-1}
(\pm c_{n_1} + c_{n_2})\sigma(v_{n_2} (x)).
\ee
Which becomes:
\be{merge-form-2}
\pm c \sigma(v(x)) = c \sigma (\pm v(x)).
\ee
The connection weight $n_2 \Longrightarrow out-layer$ becomes:
\be{weight-update-1}
c^{new}_{n_2} = \pm c_{n_1} + c^{old}_{n_2}
\ee
The above modification will not alter the original I/O mappings.

\br{second-remark}
As we shall see in the next section, conditions (I') and (II') resemble case(1) and
case(2) of Chester's lemma (3).
\er

(III') Again from (Figure 1), if $v_j$ is a constant (i.e $\equiv k$) then remove
the jth node and change bias $\Longrightarrow$ output weight to become:
\be{weight-update-2}
c^{new}_0 = \sigma(k) + c^{old}_0
\ee
where $\sigma(k)$ is a tanh of constant $k$.

\bd{net-classes}
${\cal N}_{m,num,1}$ is a set of feedforward nets ---see Figure 1--- where $m$ denotes the size
of the input, $num$ is the size of the hidden layer, and only a single output.
${\cal PLN}$ denotes the class of piecewise linear feedforward networks.
\ed

\br{third-remark}
The main results of the uniqueness principles are presented in thm 2.1 of \cite{Sussmann-91}.
\er

\subsection{{\cal PLN} simplification and existing correspondence with Sussmann's reducibility
and equivalence}

One particular point of interest is lemma(3) of network simplification in \cite{Chester-91-draft}
stated {\it Two overlapping neurons in the same layer of a piecewise linear network 
can be replaced by one or two non-overlapping neurons without changing the function
computed by PLN}.

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

The above results address the approximation/interpolation issues using a single
hidden layer network, but our investigation will deal with the approximation issue
using various depth and breadth (or width) feedforward networks.
A key question we hope to answer
is the relationship (if any) between network architecture and the function(s) to be 
approximated. Particularly, we are interested in finding out the type of unit
functions of the network that yield as close an approximation to the target
function(s) as possible. As a side note, the above theorem (\ref{Cybenko-89-theorem}) 
is strictly for continuous functions. An example of those functions that are not
network computable is:
\bex{example1}
$g:\R^n\rightarrow \R$ such that
$$
g(r) =
\twoif {1} {\text{if} r\;\;is\,\,rational}
       {0} {\text{if} r\;\;is\,\,not\,\,rational}
$$
\eex
Before tackling the issue we set out to do, let us briefly examine another
relevant result. K. Hornik, H. White and M. Stinchcombe \cite{Hornik} 
presented the following schema (with a slight difference in notation from the above work):
Given a feedforward network with a $G : \R^n\rightarrow \R$ type hidden layer. The hidden
units are semi-affine because they process their input via a $G\cdot A$ composition,
where $A : \R^n\rightarrow \R$ is an affine map $A(x) = (w,x) + b$. The variable $x$ 
stands for the input vector, $w \in \R^n$ for the weights vector, 
$b$ for a scalar bias parameter 
and $(w,x)$ is an inner product. Given this scheme, the major result of the paper is
summarized as follow: Any real-valued continuous function with compact domain can be 
arbitrarily closely approximated by a network of the above type provided a sufficient number
of $G\cdot A$ hidden units.

From an approximation theoretic point of view (see Lorentz \cite{Lorentz} and Rice \cite{Rice}), 
the issues summarized above, is to approximate or interpolate
(see Sontag\cite{Sontag1}\cite{Sontag2})
a continuous function $f(x)$ by an approximating function $F(A,X)$ having a fixed
number of parameters $A$, ($A$ and $X$ are real vectors $A = <a_1,\ldots ,a_m>$, 
$X = <x_1,\dots ,x_n>$)
in an ordinary n-dimensional Euclidean space. Now, the learning step can be summarized as follows:
For a choice of certain $F$, the problem is then to find the set of parameters
$A$ that provides the best possible approximation of $f$. A multilayer feedforward
network with fixed non-linearities 
is a particular $F$, and the weights in the network correspond to the parameter vector
$A$. It is quite important to choose an approximating function $F$ that is as ``compatible''
as possible with $f$. Thus just as important as the problem of how to learn a mapping
is the problem of choosing a network that is powerful enough to represent the mapping.

The motivation behind using hybrid structures is the recent work of
Eric Baum \cite{Baum-90}. His work utilizes a learning algorithm to yield a hypothesis
network of two hidden units, one linear and the other quadratic threshold. Furthermore,
he stated that 
{\it ``...It has frequently been marked [sic] that a shortcoming of neural net models
is that they typically involve one type of neuron, whereas biological brains use many 
different types of neurons... It seems reasonable to hope that neural nets using
mixtures of linear threshold and more complex neurons can be useful in various contexts''}.

\section{More on the Problem of Approximation via Multi-layer Nets}

The first thing that need to be stated is : How do we measure the ``best
possible approximation'' of $f$ ?

From the work of J. Rice \cite{Rice}, let $\rho$ be a distance measure to determine the
distance $\rho [f(x), F(A,X)]$ of an approximation $F(A,X)$ from $f(x)$. 
$\rho [x,y] = {\norm{x -y}}_2$ in $L_2$-norm.
In short, the {\it Approximation Problem} can be stated as follows:

If $f(x)$ is a continuous function defined on set $X$, and $F(A,x)$ is an approximating
function that depends continuously on $A \in P$ ($P$ is the parameter space or set in
the n-dimensional Euclidean space $E_n$) and $X$, the {\it approximation problem} is to 
determine the parameters $A^*$ such that:
\be{best-approximation}
\rho [F( A^*,x),f(x)] \leq \rho [F(A,x),f(x)] \;\;\;\;\; \forall A ( A \in P).
\ee

Also it can be stated in the following way:

{\it Given a function $f$ belonging to some prescribed set of functions $\Phi$, and given a subset
$A$ of $\Phi$, find the element $a$ of $A$ that is the closest to $f$}.

A solution to the above problem, if it exists, is said to be a {\it best approximation}.
The existence
of such a solution depends heavily on the class of functions to whom $F(A,X)$
belongs (see \cite{Rice}. Let $F(A,X) : \R^n \rightarrow \R$, from the multilayer
network's side, we have the following approximation cases:

(1) Linear : 
$$
F(A,X) = W \cdot X
$$
where $W$ and $X$ are n-dimensional vectors. This corresponds to a net without hidden nodes.

(2) Linear in some suitable basis of functions (i.e ${\{\Phi_i \}}_{i=1}^m$ ) of the 
original inputs $X$ :
$$
F(A,X) = \sum_{i=1}^m \, A_i \Phi_i (X)
$$
and corresponds to a network with one hidden layer. Depending on the values of $\Phi_i$,
$F(A,X)$ can be a polynomial as we shall see later. Spline interpolation used by Stone
\cite{Stone-85} ,to estimate the additive functions, fits in this case. (Also, see 
J. Friedman's \cite{Friedman})

(3) Nested sigmoidal scheme which can be written :
$$
F(A,X) = \sigma (\sum_n \, a_n \sigma (\sum_i \, v_i \sigma 
(\ldots \sigma(\sum_j \,u_j X_j)\ldots )))
$$
This scheme corresponds to a multilayer network with weights $A = {w_n , v_i , u_j ,\ldots}$.
The motivation of this nested structure is :
$$
F(A,X) = \sigma (\sum_n \, w_n \sigma (\sum_j \, u_j X_j))
$$
with $\sigma$ being a linear threshold function, can represent all Boolean functions
(any  $S: {\{0,1\}}^N \rightarrow {\{0,1\}}$ can be written as a disjunction of conjunctions,
which in terms of threshold elements becoms the above expression, where biases or dummy
inputs are allowed). 

In each of these schemes, in order to get the best approximation we need to  minimize the measure
($\rho$) over the given set of training examples. It has been shown by numerous existing
work that a general approximating representation can be obtained from the use of the above
second or third scheme.

\section{Objectives, Definitions and Examples}

\subsection{Issue One}

The above two works of Cybenko \cite{Cybenko1-89}, White, etl.\cite{Hornik} and some others deal with
non-linearities in the form of continuous-valued functions (i.e sigmoid or logistic
squashing types). From the set of bounded measurable functions which include
bounded continuous as well as those with countable number of discontinuities,
we will be focusing on the discontinuous category. One of these discontinuities is
the step function. Also we will address the issue
of how discontinuous functions can affect (positively or negatively) the network
ability to learn or function-approximate.
Another work of interest here is that of N. Cotter\cite{Cotter},
which deals with continuous functions in the context of the Stone-Weierstrass theorem. 
There is no restriction imposed on the number of hidden layers, though the work of
Cybenko and White cited above deal with single hidden layer networks. 

Two points about the issue of using multi-hidden vs single-hidden layer(s) network is:

First, in general, unless the target geometry requires hyperplane cuts that are linearly
dependent (thus reducing the degrees of freedom), a single layer of hidden units
is sufficient for arbitrary feature-space partitioning. Also, as recently shown
by Kurt Hornik \cite{Hornik-91}, that if the hidden units' activation function is
an arbitrary bounded and nonconstant then the network can operate as a universal
function approximator w.r.t $L^{p} (\mu)$ performance criteria, for arbitrary finite 
input environment measures ($\mu$), provided that {\it sufficiently many hidden units}
are available.
%%%%% Sontag2 ref is SYCON-90-11

Second, it has been shown by , among others, Sontag\cite{Sontag2} that on-hidden layer
is not sufficient to achieve stabilization when the net is utilized as a controller of
a non-linear system, but a two-hidden layers should be enough. Also, prior to \cite{Sontag2},
D. Chester\cite{Chester-90} had noted the need for two hidden layers. While he \cite{Chester-90}
stated his results mostly in terms of numerical accuracy and numbers of neurons,
we strongly suspect that the underlying reasons also had to with limitations 
of function superpositions !!. George Cybenko in \cite{Cybenko2-89} has stated that
``$\ldots${\it there are numerous convincing heuristic arguments that suggest networks
with more than one internal layer may be more parsimonious and easier to train}''. 
He proceeded in \cite{Cybenko2-89} to utilize a two-hidden-layer network for his
experiments.

\subsection{Issue Two}

On the question of approximation and best approximation, here are some formalities:

\bt{weierstrass-app-thm}
(D. Sprecher (p. 205)\cite{Sprecher})\\ The set $P({\cal A})$ of polynomials on ${\cal A}$ with
coefficients in $\R$ is dense in ${\cal C}({\cal A})$ : Given an arbitrary function
$f \in {\cal C}({\cal A})$ and a number $\epsilon > 0$, then there is a polynomial
$p \in P({\cal A})$ with the property that $\norm{f - p} < \epsilon$.

(Gelbaum and Olmsted (p. 304)\cite{Gelbaum}):\\ If ${\cal K}$ is a compact subset of $\R^n$,
$\epsilon > 0$, and $f \in {\cal C}({\cal K},{\cal R})$ then there is a polynomial 
$p : \R^n \rightarrow \R$ such that on ${\cal K}$, $|f - p| < \epsilon$.
\ets

Another form of theorem (\ref{weierstrass-app-thm}) is given in G. Lorentz's (\cite{Lorentz}) as
follows:

\bt{weierstrass-app-thm-lorentz}
A continuous function $f(x_1,\ldots,x_k)$ defined on a compact subset ${\cal A}$ of the
euclidean k-space, is approximated (or approximable) by polynomials in $x_1,\ldots,x_k$.
\ets

What will be of interest to us here is the extension to the above Weierstrass theorem, which
is called the {\it Stone-Weierstrass} theorem:

\bt{stone-weierstrass-thm}
(from Royden (p. 174)\cite{Royden})\\ Let $X$ be a compact space and $A$ an algebra of continuous
real-valued functions on $X$ which separates the points of $X$ and which contains the 
constant functions. Then given any continuous real-valued function $f$ on $X$ and any
$\epsilon > 0$ there is a function $g$ in $A$ such that for all $x$ in $X$ we have
$|g(x) - f(x)| < \epsilon$. In other words, $A$ is a dense subset of $C(X)$.
\ets

For more details (i.e proofs) about the above theorems and definitions ,
see {\it Rudin's Principles of Math Analysis 
\cite{Rudin} ,D. Sprecher's Elements of Real Analysis \cite{Sprecher} and Lorentz's Function
Approximation\cite{Lorentz} , and H. Royden's Real Analysis \cite{Royden} }.

\subsection{Issue Three}

It has been shown by various researchers (e.g. see Cybenko \cite{Cybenko-90}) that for specific
classification problems, the network architecture plays a key role in determining the quality
of a solution (as measured both by interpolation and extrapolation). The point here is how
do we approximatly formalize or put together an architecture to yield a good 
approximation/solution to our target function(s)? 

Well, it is known that the space of possible feedforward nets is discrete and easily ordered in
many natural ways so we could propose some kind of a network modification technique. This technique
will allow transitions to take place between neighboring network architectures with the goal of
minimizing an {\it objective function} that consists of some combination of the training {\it data
error}, {\it generalization error}, and {\it penalty term} for lack of parsimony or for being
not very optimal (i.e nodes and connections used may be more than needed !). It is possible
to think of such an objective function as a kind of linear programming ``cost function''.

\bd{objective-func-dfn}
Let ${\it Net}_1 \Longrightarrow \ldots \Longrightarrow {\it Net}_n$. The transfer criteria 
between ${\it Net}_i$ and ${\it Net}_{i+1}$ is the function:
\be{obj-equation}
f(D_{\alpha},G_{\beta},P_{\gamma}) \equiv D_{\alpha} \odot G_{\beta} \odot P_{\gamma}
\ee
where $\odot$ is some binary operation. $D_{\alpha}$ is data error, $G_{\beta}$ is generalization
error, and $P_{\gamma}$ is some penalty term. The goal is to minimize (\ref{obj-equation})
w.r.t the given parameters.
\ed

At this point, it is necessary to point out that the above transformation needs to preserve
network equivalence. This criterion is quite important and a recent work of Sussmann 
\cite{Sussmann-91} examines network equivalence from the point of view of net 
reducibility and irreducibility. Sussmann's work deals with single hidden layer networks
with hyperbolic tangent transfer functions in both hidden and output layers.
An extension to this work is to determine whether the conditions of network irr/reducibility
stated in \cite{Sussmann-91} hold when dealing with networks having non-sigmoidal
or non-hyperbolic tangent nodes. Two possible node functions to consider are linear
and threshold functions. Networks with hidden layer(s) of threshold nodes are quite
useful, as shown by the work of E. Baum\cite{Baum-91}. Furthermore, he \cite{Baum-91}  
indicated that the generalization of his methods to sigmoid nets may be straightforward.
Moreover, in case one wants to have the capability to generate real-valued queries at the
higher layers of a multilayer net, then it is preferable approach to train nets which
are composed of sigmoid functions, rather than linear threshold units.

The reason in mentioning the work of \cite{Baum-91} is that we need to
determine whether the extension to \cite{Sussmann-91} stated above
applys in one way or another to the inverse transformation from threshold units type nets
to those with sigmoid units.


\bd{various-net-architectures}
Some classes of the feed-forward nets of interest to us are:

(1) A multi-layer net to represent any polynomial mapping, with polynomial output
functions of at least order $2$ for each unit, and ``enough'' hidden units and layers.
\be{net-1}
In:(x_1 \ldots x_n) \Rightarrow 
Hidden:(y_1 \ldots y_m) \Rightarrow \dots
\Rightarrow Out:(z_1 \ldots z_k)
\ee
for example, each $z_i$ is equavilent to $a \cdot x + b \cdot x^2 + c \cdot x^3$.

(2) Two-layer networks with an unrestricted number of sigmoidal units on the first
layer and a linear unit on the second layer.
\be{net-2}
(In) \Rightarrow Layer:sigmoidal (h_1 <x> \ldots h_m <x>)
\Rightarrow (Out): linear.
\ee
The function implemented is :
\be{net-2-func}
\sum_j \beta_j h(\sum_{k=1}^d \alpha_{jk} x_k + \alpha_{j,o})
\ee

(3) Three-layer nets with linear nodes on the first layer, polynomial nodes in one variable on
the second layer, and a linear unit on the third layer.
\be{net-3}
(In) \Rightarrow Layer:linear \Rightarrow
Layer: poly (g_1 <x> \ldots g_n <x>)
\Rightarrow (Out):linear .
\ee
The function implemented is:
\be{net-3-func}
\sum_j \beta_j g_j (\sum_{k=1}^d \alpha_{jk} x_k ) 
\ee

(4) Four-layer networks with polynomial units in one variable on the first and third layers, linear
units on the second and fourth layers.
\be{net-4}
(In) \Rightarrow poly (g<x> \ldots g<x>)
\Rightarrow linear \Rightarrow
poly (g<y> \ldots g<y>)
\Rightarrow (Out): linear.
\ee
The function implemented is :
\be{net-4-func}
\sum_{j=1}^{2d+1} \beta_j g_j (\sum_{k=1}^d \alpha_{jk} g_{jk}(x_k))
\ee

(5) Polynomial networks with constrained number of units and unrestricted number of layers. 
The functions
implemented are arbitrary polynomials in $d$ variables.
\ed

\subsection{Issue Four}

On the question of function complexity, let's assume our invariant target function (see next
section) is drawn and applied over some ``recognition space'', how do we measure the complexity
of such function?

Utilizing the classification complexity of Cybenko, an approximate measure can be
derived, though not easily. Minsky and Papert \cite{Minsky} suggest that natural
``visual functions'' have low {\it order of complexity}. They go about defining such
measure in terms of the {\it order of a function}, where function of order $q$ is one
that can be computed from partial predicates, each of which depend on no more than
$q$ elements in the {\it input vector}. In addition to these measures is a complexity
metric represented by the number of patterns for which the target function is defined.

A point that is worth stating is the fact that a number of reseachers have pointed out
the close correlation between backpropagation learning and the learned/approximated
function complexity. In other words, they've noted that back-prop learning is
biased toward low complexity functions and these functions are independent from
other parameters of the learning process such as the length of the {\it input vector}.
As it has been pointed out , from various simulations, that for functions of low
order of complexity, variations in input size have relatively small effects on generalization
performance. Furthermore, for more complex functions, there is a clear relation between
the size of the initial {\it hypothesis space} and learning difficulty. Also the number
of functions/sub-functions in the given {\it hypothesis space}, which approximate to
some degree our target function , is quite relevant to the complexity measure.
One possible question that can be asked is , why do we need these complexity metrices?
An answer to this is that these metrices can be used to estimate the degree to which a function
can be encoded in a compact, and hopefully efficient form. It is usually the case that
function encodings can be made more compact by limiting connectivity between layers
above the input layer (or below it, depending on which way you look at the net).
Now , we could ask if the above complexity measures could contribute to making
function encoding more efficient (?!).

\section{The Basic Methodology}

The technique adapted here is to formulate polynomial expressions, using certain network structures,
and then with the help of 
{\it Weierstrass Approximation Theorem (WAT)}(theorem \ref{weierstrass-app-thm})
and the {\it Stone-Weierstrass Theorem (SWT)}(theorem \ref{stone-weierstrass-thm}) the 
target function is approximated by the given polynomial. The target functions are those of the
set of measurables.
%%
%% One specific type of function we need to approximate is the vector-valued
%% functions. The other is piecewise continuous (bounded with a countable number of discontinuities).
%% Clearly and from the definitions and theorems of the previous section, these
%% two function categories belong to the bounded and measurable functions' set.
%%
The approximation will heavily depends on the structure of the network and the function(s)
composing it. Neil Cotter\cite{Cotter} proposed a hybrid network structure and named it
{\it Modified Logistic Network (MLN)}. Furthermore, he indicated that MLN can be used to construct
various polynomial expressions , and via SWT, approximate different functions from the
set of bounded and measurables.
Our work here is to make use of network structures similar to those of MLN to build
appropriate polynomials , armed with the tools of WAT, the approximation of the proposed 
function becomes possible.

One major difference between our proposed structure and that of MLN is that
we will not confine ourselves to only one function type per layer. In other words,
any particular layer of our network can carry more than one class of functional
nodes.

A very important component of our work is the target function $f$. In order to
make things simple we shall assume that $f$ carry the property of {\it invariance}. For example,
if we take an image of some alphbet character (i.e $A,a,B,b,\ldots$) then scaling, shifting
or rotating it won't change the basic identity of the image itself. The category of functions $f$
we are interested in approximating are invariant over the space of the given image(s). 
A simple formalism of this property goes as follows:

\bd{invariance-property-dfn}
A set ${\cal B}$ of subsets $B_1,\ldots,B_i ,\ldots, B_n$, where ${\cal B}$
is a subset of the overall space ${\cal X}$ (i.e ${\cal X} = {1,2,3,\dots}$ and 
${\cal B} \subset {\cal X}$), such that if $x_i \in B_i$ and $x_j \in B_i$ then $f$ is 
{\it invariant} within each set $B_i$ of ${\cal B}$ and $f(x_i) = f(x_j)$.
\ed

For example, let ${\cal X}$ be a set of images, $f$ the recognition function(s) of ${\cal X}$ 
and share some scale of invariance. In this case, each set $B_i \in {\cal B}$ consists of
images which are scaled versions of one another. To narrow the category of $f$ further, we
will assume it belongs to the {\it vector-valued class} of functions. This calls for a bit
of formalism:

\bd{vector-valued-dfn}
Vector-valued functions are those functions with valued in $R^k$, which is the euclidean
$k$-space. It is known that $R^k$ will contain with other things 
all ordered $k$-tuples (e.g $x = (x_1,\dots,x_k)$) for $k > 1$.
{\it Note}: 
Let's assume that $R^k$ is a proper subset of the $n$-dimensional structure $\R^n$ mentioned
above in this paper.
\ed

The ``image'' concept used here is nothing but an example and in general  
the {\it target function} can be applied to various ${\cal X}$s ,in other words,
$f$ can be drawn over a wider class with various properties.

\subsection{Some Notes About PolyNets}

Most of the forms that have been proposed for learning networks are parametric elements
taking on of the following forms: 
\be{param-1}
g(z, \theta) = h(\sum_k \theta_k z_k + \theta_0)
\ee 
\be{param-2}
g(z, \theta) = \sum_k \theta_k \varphi_k (z)
\ee
or, more generally,
\be{param-3}
g(x, \theta) = h(\sum_k \theta_k \varphi_k (k))
\ee
where $\varphi_k , k=1,\ldots,m$, and $h$ are fixed functions. The most two common
choices for the $\varphi_k$ are linear terms (or what is so called {\it coordinate functions}
\cite{Rudin}), so that the sum simply implements a linear combination of the inputs as in
(\ref{param-1}), or {\it polynomial terms} of moderate degree. The nonlinear function
$h$ can take different forms among them a unit {\it step function}.
One important result with relevance to our work is that of G. Lorentz\cite{Lorentz}. He 
points out that WAT and its generalization to multivariate functions asserts that
any continuous function on $[0,1]^d$ can be uniformaly approximated by a sufficiently large
degree polynomial. The polynomial approximations need not be restricted to the canonical sum
of products form $\sum_k \theta_k x_1^{k_1} , \ldots , x_d^{k_d}$ (which is itself a large
network of simple structure).

Other multivariate forms are known to approximate arbitrary continuous functions. For instance,
finite trigonometric sums $\sum_k (\alpha_k cos(\pi k \cdot x) + \beta_k sin(\pi k \cdot x))$ can
uniformly approximate any continous function on $[0,1]^d$, 
provided the function is continuously extended
to satisfy boundary conditions on $[-1,1]^d$ (See Lorentz \cite{Lorentz} p.87). Here 
$k = (k_1 \ldots k_d)$ and $k\cdot x = \sum_j k_j x_j$. Since the (sin) and (cos) functions
have bounded variation, so they can be represented as the difference of monotone functions
(h). Consequently, the trigonometric sum
is a two-layer network with first layer elements having the form(\ref{param-1}). This gives
a simple proof of Cybenko's theorem specialized to such (h).

More other aspects of polynomial approximations need to be added. One major point is determining
the class of functional units of the network that approximate the target function(s).

\subsection{Polynomial Formations in Nets: General Notes}

{\bf Note 1}\\
From a mathematical point of view, any sigmoidal non-linearities can be approximated
by a polynomial of some finite degree. Let us illustrate:
The {\it standard sigmoidal}
\be{sigmoid}
f(x) = {1 \over 1 + e^{-x}}
\ee
Via {\it Taylor's Series} expansion up to some $n \in {\cal N}$ we get:
\be{TS-expan}
e^{-x} = 1 - x + {x^2 \over {2!}} - {x^3 \over {3!}} \ldots +(-) {x^n \over {n!}}
\ee
Substituting (\ref{TS-expan}) in (\ref{sigmoid}) we get:
\be{sig-poly}
f(x) = {1 \over 2} - x^{-1} + {{2!} \over x^2} - {{3!} \over x^3} \ldots +(-) {{n!} \over x^n}
\ee
which is a polynomial of degree $n$.

{\bf Note 2}\\
In regard to the issue of {\it polynomial order}, we take note from the work of Hanson and
Burr\cite{Hanson90}. Given the following polynomial form (in 2-dim space):
\be{poly-form1}
f(<x>) = \sum_i \sum_j x_i x_j w_{ijk} + {x_i}^{\alpha_i} + {x_j}^{\alpha_j} +(-) \theta_k
\ee
which forms a {\it polygonal boundary} geometrically, but going up to 3-dim the shape
becomes a {\it polyhedron} and if we go up to n-dim it becomes a {\it hyperpolygon},
according to Hanson and Burr\cite{Hanson90}.
Hanson and Burr state that with the hidden units non-linearities ,(looking at the problem
from a geometric point of view as in Cover\cite{Cover}), the feature space can be
partitioned into what is called ``decision boundaries''. Again, following the work of
Cover\cite{Cover} and Winder\cite{Winder}, using simple polynomial units the network can
produce various and arbitrary boundaries over the target space. Such boundaries require
polynomials of arbitrary degree. For example, an r-th order polynomial can be stated
recursively as follows:
\be{poly-form2}
D^r (<x>) = \sum_{p_1 = 1}^n \sum_{p_2 = p_1}^n \ldots \sum_{p_r = p_{r-1}}^n 
w_{p_1 p_2 \ldots p_r} x_{p_1}x_{p_2}\ldots x_{p_r} + d^{r-1} (<x>)
\ee
can be conveniently adapted to be a unit ``fan-in'' function. The $n$ of the summations
stands for the dimension of the feature space. For the sake of simplicity, we won't go
higher than 2-nd order polynomials which include ``spherical'' and ``quadratic units''.
Also it is assumed that $n =2$. Such an example will be:
\be{poly-form3}
D^{2} (<x>) = \sum_{p_1 = 1}^2 \sum_{p_2 = 1}^2 w_{p_1 p_2} x_{p_1} x_{p_2} + D^{1} (<x>)
            = w_{11} {x_1}^2 + w_{12} x_1 x_2 + w_{22} {x_2}^2 + w_1 x_1 + w_2 x_2 + w_0
\ee
For larger $n$ and $r$, more complex ``boundaries'' can be formed.
(See the work of Cover\cite{Cover})
The above polynomial forms (\ref{poly-form1} ,\ref{poly-form2}, \ref{poly-form3}) can be 
formed by multi-layer nets with hidden non-linearities (i.e. logistic type from considering
the Taylor expansion of the exponentials).

In short, what we're after here is networks with logistic units or/and other non-linearities
to construct some fixed order(s) polynomials of terms and cross-terms which in turn 
approximate the target function.

{\bf Note 3}\\
In regard to those neural nets with {\it quadratic} discriminant functions such as
\be{quad-form}
f(x) \approx w_0 + \sum_{i=1}^d w_i x_i + \sum_{i=1}^d \sum_{j=1}^d w_{ij} x_i x_j
\ee
the formation of polynomials is straight forward procedure given this kind of
units. 

The work of Cybenko, stated above, and the more recent work of his \cite{Cybenko-90}
which addresses the question of network's data interpolation and functional approximation
deal with single-hidden-layer nets of non-linear and continuous (but not necessarily
monotonic) sigmoidal functions. Briefly from Cybenko's \cite{Cybenko1-89}: Let $I_n$ be an n-dim
unit cube $[0,1]^n$ and $C(I_n)$ is the space of continuous functions on $I_n$. Also let
$\norm{f}$ be the {\it supremum} norm of function $f$ which belongs to $C(I_n)$. Now the
interpolation concept can be formulated as determining those conditions under which the
sums of
\be{out-func-form}
G(x) = \sum_{j=1}^N \alpha_j \sigma ({y_j}^T x + \theta_j)
\ee
are {\it dense} in $C(I_n)$ w.r.t $\norm{f}$. The form of $G(x)$ function is precisely the
form of the output function of the given network. Using the main theorem of \cite{Cybenko1-89}
,and again given a single hidden layer net, the parameters of this net can be chosen to
achieve any ``desired modelling error''. This last statement addresses the issue of function
approximation by the given network. 

Certainly, n-degree polynomials play a useful part in formulating the concept of network
interpolation/function approximation. From the work of Lorentz\cite{Lorentz}: Let
$\Phi : \phi_1 \ldots \phi_n$ be a class of real-valued functions on a set ${\cal A}$ ``closed
and bounded''; let $x_1 \ldots x_n$ be given distinct points of ${\cal A}$; let
$c_1 \ldots c_n$ be given real numbers. Then the polynomial $P(x) = \sum_{i=1}^n a_i \phi_i (x)$
is said to interpolate the real values $c_k$ if $P(x_k) = c_k$, $k=1 \ldots n$. Usually,
the $c_k$ are values at the points $x_k$ of some given function $f(x)$, then $P(.)$ is said
to interpolate $f(.)$. Let polynomials $q_k (x)$, $k=1 \ldots n$ s.t $q_k (x_k) = 1$,
$q_k(x_i) = 0$ and $i \neq k$, $i, k =1 \ldots n$. Then an interpolating polynomial can be
formed as:
\be{interp-poly}
P(x) = \sum_{i=1}^n c_i q_i (x) = c_1 q_1 (x) + c_2 q_2 (x) + \ldots + c_n q_n (x) 
\ee

\section{Computer Simulations of Some Existing Hybrid Nets}

Two models will be tried out and the results will be compared with those obtained
from non-hybrid models :

First, the {\it Kolmogorov-Lorentz Network} as put together by A. Barron \cite{Barron}.
The architectural form of this net implements a two-function composition along with
their summation. Topologically, the network consists of four layers of units representing
the inner function, its summation, the outer function, and the overall summation.
A look-alike to this topology is a tree-structured network proposed by N. Cotter \cite{Cotter}
and coined it to be the {\it modified logistic network (MLN)}. 

Second, the four classes of networks (see {\it definition} \ref{various-net-architectures}) 
which satisfy the {\it Network Approximation Theorem} of Barron \cite{Barron}.
The major reason they do so because they
are dense in the space of continuous functions on compact subsets of some n-dimentional
Euclidean space, in the sense that for any such function $f^*$ there exists a sequence
of network functions $f_n$ that converges uniformly to $f^*$. 

\section{Conclusion}

There are a number of concepts in this paper that need to be worked out and then presented
in a more detail. To narrow the scope of this investigation, some points stated above
may have to be set aside for future research.

\newpage
\begin{thebibliography}{HSW}

\bibitem[HSW-89]{Hornik}
Hornik, K.M., M.\ Stinchcombe, and H.\ White, 
``Multilayer feedforward networks are universal approximators,''
{\it Neural Networks} {\bf 2}, 1989, p.\ 359-366.

\bibitem[Suss-91]{Sussmann-91}
Sussmann, Hector,
``Uniqueness of the weights for minimal feedforward nets with a given a given
input-output map,'' {\it Report SYCON-91-06a}, Rutgers Center for Systems and
Control, Rutgers University, May 1991.

\bibitem[Ch-90]{Chester-90}
Chester, Daniel,
``Why two hidden layers are better than one,'' {\it Proc. International Joint 
Conference on Neural Networks}, Washington, 1989, IEEE Publications, NY, 1989,
{\bf vol-1}, pp.\ 265-268.

\bibitem[Ch-91]{Chester-91}
Chester, Daniel,
``The Generalization Capabilities of Feedforward Neural Nets,''-DRAFT 1991,
and {\it DIMACS Neural Nets Workshop presentation, May 1991}.

\bibitem[Horn-91]{Hornik-91}
Hornik, Kurt,
``Approximation Capabilities of Multilayer Feedforward Networks,''
{\it Neural Networks} {\bf 4}, 1991, p.\ 251-257.

\bibitem[GO-90]{Gelbaum}
Gelbaum, B. R, and J.\ Olmsted,
{\it Theorems and Counterexamples in Mathematics},
Springer-Verlag, New York, 1990.

\bibitem[Rice-64]{Rice}
Rice, John R.,
{\it The Approximation of Functions}, vol-1,
Addison-Wesley, Reading, Mass, 1964.

\bibitem[Lor-66]{Lorentz}
Lorentz, G. G.,
{\it Approximation of Functions},
Holt-Rinehart-Winston, New York, 1966.

\bibitem[Roy]{Royden}
Royden, H. L.,
{\it Real Analysis}, 3rd edition,
The Macmillan Company, New York, 1988.

\bibitem[Rud]{Rudin}
Ruden, Walter,
{\it Real and Complex Analysis}, 3rd edition,
McGraw-Hill Inc., New York, 1987.

\bibitem[Spre]{Sprecher}
Sprecher, David A.,
{\it Elements of Real Analysis},
Academic Press, New York, 1970.

\bibitem[Krug-91]{Kruglyak-91}
``How to solve the N bit encoder problem with just two hidden
units,'' Preprint ,January 1991.

\bibitem[Cyb1-89]{Cybenko1-89}
Cybenko, George,
``Approximation by superpositions of a sigmoidal function,''
{\bf CSRD-856}, Center for Supercomputing Research and Development,
Univ. of Illinois, Urbana,IL (Feb 1989).

\bibitem[Cyb2-89]{Cybenko2-89}
Cybenko, George,
``Mathematical Problems in Neural Computing,''
In Proceedings of the International Symposium MTNS-89, Amsterdam, 1989.

\bibitem[Cyb-88]{Cybenko-88}
Cybenko, George,
``Continuous valued neural networks with two hidden layers are sufficient,''
{\bf CSRD-935}, Center for Supercomputing Research and Development,
Univ. of Illinois, Urbana,IL (March 1988).

\bibitem[Cyb-90]{Cybenko-90}
Cybenko, George,
``Complexity Theory of Neural Networks and Classification Problems,''
Center for Supercomputing Research and Development,
Univ. of Illinois, Urbana, IL (April 1990).

\bibitem[Sont1-90]{Sontag1}
Sontag, E,
``Feedback stabilization using two-hidden-layer nets,'' {\it SYCON Report},
Rutgers University, 1990.

\bibitem[Sont2-90]{Sontag2}
Sontag, E,
``On the recognition capabilities of feedforward neural nets,'' {\it SYCON Report},
Rutgers University, 1990.

\bibitem[Sont3-91]{Sontag3}
Sontag, E,
``Feedforward nets for interpolation and classification,'' {\it SYCON Report},
Rutgers Univ., 1991.

\bibitem[Sont4-91]{Sontag4}
Sontag, E,

\bibitem[GPC]{Girosi1-90}
Girosi, F, etl.

\bibitem[GP-90]{Girosi2-90}
F. Girosi, etl.

\bibitem[PG-89]{Poggio-89}
Poggio, T, and F. Girosi,

\bibitem[Baum-90]{Baum-90}
Baum, Eric,
``A polynomial time algorithm that learns two hidden unit nets,''
{\it Neural Computation}, {\bf vol.2}, {\bf No.4}, Winter 1990.

\bibitem[Baum-91]{Baum-91}
Baum, Eric,
``Neural Net Algorithms That Learn in Polynomial Time from Examples and Queries,''
{\it IEEE Trans. on Neural Networks}, {\bf vol.2}, {\bf No.1}, January 1991.

\bibitem[JF-90]{Friedman}
Friedman,Jerome,

\bibitem[Cot-90]{Cotter}
Cotter, N,
``The Stone-Weierstrass Theorem and Its Application to Neural Nets,''
{\it IEEE Trans. on Neural Networks}, {\bf vol.1}, {\bf No.4}, December 1990.

\bibitem[HB-90]{Hanson90}
Hanson, S, and Burr,

\bibitem[Sto-85]{Stone-85}
Stone,C.J

\bibitem[Bar-88]{Barron}
Barron, Andrew and R.\ Barron,
``Statistical learning networks: a unifying view,''
{\it Computing Science and Statistics: Proc. 20th Symp. Interface}, Ed Wegman, editor,
American Statistical Association, Washington, DC., pp.\ 192-203, 1988.

\bibitem[Win-66]{Winder}
Winder,T

\bibitem[Cov-65]{Cover}
Cover, Tom

\bibitem[Min-88]{Minsky}
Minsky, Marvin and S Papert,

\bibitem[DIMACS-91]{Dimacs-workshop}
Sussmann, Sontag, and Kuhn,

\bibitem[Maass]{Maass-91}
Maass, Schnitger, and Sontag 1991.

\end{thebibliography}

\end{document}








