%% LATEX TWICE TO GET THE REFERENCES RIGHT
%%
%% \documentstyle[11pt,psfig]{article}        
%%
\documentstyle[12pt,epsf,psfig]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% macro for postscript figures - the easy way.
%% See directory ftp.cis.ufl.edu/tech report by fishwick@cis.ufl.edu 
%% This will help to control the size of the figure.
%%
\newcommand{\postscript}[2]
 {\setlength{\epsfxsize}{#2\hsize}
  \centerline{\epsfbox{#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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{itobservation}[itlemma]{Observation}
\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{observation}{\begin{itobservation}\rm}{\end{itobservation}} %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{\bo}[1]{\begin{observation}\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{\eo}{\mybox\end{observation}}
\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{\eos}{\end{observation}}
\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 SCCS report: 774}
\end{flushright}
\vfill
\begin{center} 
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{.05cm}
\hrule
\vspace{.25cm}
{\bf 
Some Issues of Reducibility and Equivalence in Feedforward Neural Networks
}
\vspace{.25cm}
\hrule
\vspace{.05cm}
\hrule
\hrule
\hrule
\hrule
\hrule
\vspace{1cm}
Saleh Elmohamed\\
Northeast Parallel Architectures Center\\
Syracuse, NY 13244-4100 , USA .\\
saleh@npac.syr.edu\\
\end{center}

\vspace{1.5cm}
\centerline{ABSTRACT}

We show how sigmoidal ($\tanh()$) feedforward net reducibility and
equivalence conditions proposed by Sussmann and later by Sontag can be
adapted to feedforward neural structures using piecewise rational
activation functions.
In addition, the uniqueness results demonstrated for the $\tanh()$
nets are shown to be applicable in part to networks of piecewise
rationals, but not to piecewise linear ({\it clipping}) networks.

\vfill
\vfill
\vfill

\newpage
\pagestyle{empty}
\tableofcontents
\listoffigures
\listoftables


\newpage

\pagestyle{plain}

\section{Sketch of the background}
\setcounter{page}{1}


\begin{figure}
\postscript{figure1.ps}{0.80}
\caption{A feedforward neural net consisting of an input layer
of $m$ ``fan-out'' nodes, a single hidden layer of $n$
computational nodes, and an output layer of $u$ computational nodes.
Each computational node carries a $\sigma$ activation function and
$\theta$ threshold.} 
\label{fig.1}
\end{figure}

Hector Sussmann \cite{8} examined network reducibility and
equivalence for the input-output mappings of a neural net. The net
structure considered by \cite{8} is a feedforward net
with single hidden layer whose nodes use a hyperbolic
tangent activation function ($\tanh$). The units of the output layer
also use $\tanh()$ activations. 

In addition, Sussman proved what is called the {\it
uniqueness theorem} in the framework of feedforward net structures.  
It is stated that {\it two irreducible feedforward nets with the same
input-output mappings are related by a transformation in ${\cal G}$},
where ${\cal G}$ is a discrete symmetric group of nets as originally
proposed by Hecht-Nielsen \cite{10}. 

The main point in \cite{8} is {\it to show that two
input-output equivalent nets must necessarily be the same net, up to
some simple internal symmetries} (more on this later).  Also, it was
pointed out that the irreducibility condition  stated in the {\it
uniqueness theorem} is needed because there is  another source of
non-uniqueness coming from the fact that a net may  contain nodes that
make no contribution whatsoever to the output. This means that there
are cases when a net can be reduced without changing the I-O map, so
the above theorem can hold only for irreducible nets. 
One major result of Sussmann's theorem is that the I-O mapping of an
irreducible net can not be obtained from another net with fewer hidden
nodes. 

\section{The main objectives}

In this paper we address two issues/questions pertaining to the above
work:
\begin{enumerate}
\item Do the {\it uniqueness} and {\it reducibility} results of 
Sussmann apply to nets with piecewise rational activation functions ? 
If so, discuss how this may come about, otherwise give an example.
\item Do the {\it uniqueness} and {\it reducibility} results of
\cite{8} apply to nets with piecewise linear activation
functions?  If so, outline this applicability, otherwise give an
example. 
\end{enumerate}

\section{Some Background on Feedforward Networks}

\subsection{Notation and Definitions}
A feedforward network such as that of Figure-\ref{fig.1} consists of
an input layer whose nodes are merely fan-outs (no processing
takes place in these nodes), one or more hidden layer(s) 
of computational nodes, and an output layer, also with one or more
computational nodes. For the rest of the discussion,
we will assume that both the hidden and output layer nodes use
the same activation function.

It will be convenient to have a uniform notation for referring to the
node input/output and weights in a feedforward network. 
Let $y_i^{[r-1]}$ the output of the i${\it th}$ node in the 
$(r-1){\it th}$ layer of the net, $w_{ij}^{[r]}$ is the connection
weight between  i${\it th}$ node in the $(r-1){\it th}$ layer and
j${\it th}$ node of the r${\it th}$ layer (the current layer), and
$\theta_j^{[r]}$ is the threshold of the j${\it th}$ node in the
r${\it th}$ layer. Each computational node of
layer $r$ yields an output of $\sigma(\sum_i w_{ij}^{[r]}
y_{i}^{[r-1]} + \theta_j^{[r]})$. 

\bd{on-sigmoid}
The function $\sigma$ is any function
satisfying the property that both  $\lim_{u\rightarrow
-\infty}\sigma(u)$ and $\lim_{u\rightarrow +\infty}\sigma(u)$ exist
and are distinct. In this context, $\sigma$ is often called a squashing
function \cite{11}. 
\ed

Typically, $\sigma$ is one of the following:
\begin{enumerate}
\item For a $(-1,+1)$ output range, the activation function is:
\be{hyperbolic-tan}
\sigma_h(x) = \tanh(x)\;\;.
\ee
\item For the output range of $(0,1)$, the activation function is:
\be{sigmoid}
\sigma_s(x) = {1 \over {1+ e^{-x}}}\;\;.
\ee
\end{enumerate}

\bo{hyper-sigmoid-ob}
$\sigma_s(x)$ is equivalent to $\sigma_h(x)$, up to
translations and change of coordinates. The relation between these two
functions is:
\be{relation}
\sigma_h(x) = 2 \sigma_s(x) - 1\;.
\ee
\eo


\bd{def-of-smooth}
We say that $\sigma$ is a {\it smooth activation function} if and
only if  
\begin{itemize}
\item $\sigma$ is a squashing function,
\item $\sigma$ has a continuous derivative everywhere (hence, $\sigma$
is continuous),
\item $\sigma$ is odd (hence, $\sigma(0) = 0$).
\end{itemize}
\ed

\bo{obs-on-smooth}
$\sigma_h$ is a smooth activation function. 
\eo

\subsection{Network Structure and the I-O Map}
Using the notation introduced above and Figure-\ref{fig.1}, given
an input vector $x = (x_1\ldots x_m) \in \R^m$, the input to the
$j$th node of the hidden layer is:
\be{In.1}
\upsilon_j(x) = \sum_{i=1}^m w_{ij}^{[2]} y_i^{[1]}\;\;.
\ee
The output of the $j^{\it th}$ hidden node is:
\be{Out.1}
y_j^{[2]} = \sigma(\upsilon_j(x) + \theta_j^{[2]})\;\;.
\ee

Next, the input of the $l^{\it th}$ node of the output layer is:
\be{In.2}
\mu_l(x) = \sum_{j=1}^n w_{ij}^{[3]} y_j^{[2]}\;\;,
\ee
and the output of this $l^{\it th}$ output node is:
\be{Out.2}
y_l^{[3]} = \sigma(\mu_l(x) + \theta_l^{[3]})\;\;.
\ee

The I-O mapping of the network is the function from $\R^m
\longrightarrow \R^u$ computed by the net.

\section{Synopsis of Sussmann's Results}

\subsection{Definitions}

\bd{net-classes}
${\cal N}_{m,n,u}$ is the set of feedforward nets with 
activation functions $\sigma$ where $m$ denotes the size of the input
layer, $n$ is the size of the hidden layer, and $u$ the size of the
output layer. 
\ed

\subsection{The Reducibility Conditions}

Given a feedforward network , we associate a linear affine function
with each node of the hidden layer as follows: 
\be{aff-func}
\gamma_j : \R^m \longrightarrow \R, \;\; \gamma_j(x) = \upsilon_j(x) +
\theta_j,\;\; \text{for} \; j=1,\ldots,n.
\ee

\bd{affine-dfn}
Let $\alpha$ and $\beta$ on $\R^m$ be linear affine functions;
if either $\alpha(x) = -\beta(x)$ or $\alpha(x) = \beta(x)$, for all
$x \in \R^m$, then $\alpha$ and $\beta$ are sign-equivalent.
\ed

Let $b_{ij}$ be the weight between node $i$ of the input layer and
node $j$ of the hidden layer, and $c_{jk}$ be the weight between
node $j$ of the hidden layer and node $k$ of the output layer.
As outlined in \cite{8}, a feedforward network is reducible
if one or more of the following conditions hold:

\begin{enumerate}
\item
 For some $j=1,\ldots,n$ and all $k \in \{1,\ldots,u\}\;$,
 $c_{jk} = 0$.
\item
 There exist two different indices $j_1, j_2 \in \{1,\ldots,n\}$ such
 that the functions $\gamma_{j_1}$ and $\gamma_{j_2}$ are
 sign-equivalent (i.e. $\gamma_{j_1} = \pm \gamma_{j_2}$).
\item
 One of the functions $\gamma_j$ , for $j \in \{1,\ldots,n\}$, is
 constant. 
\end{enumerate}

Next we briefly examine each of the above three cases.

\bi
\item
{\it (First case)}: 
Node $j$, of the hidden layer, and all its connections can be
removed without any effect on the network output.
\item
{\it (Second case)}: Let $\rho \in \{-1,+1\}$ and $\gamma_{j_1} =
\rho\gamma_{j_2}$. Since $\sigma$ is an odd function, $\sigma(\rho
s) = \rho \sigma(s)$.
Remove node $j_1$ and all its connections, then change the output
weights for $j_2$ to: 
\be{weight-update-1}
c^{new}_{j_2 k} = \rho c^{old}_{j_1 k} + c^{old}_{j_2 k}\;\;.
\ee
The above modification will not alter the original I-O mapping.
\item
{\it (Third case)}: In this case all the weights between the input
layer and node $j$ are zero, so node $j$ is removed and thresholds of
the output nodes are properly adjusted.
\ei

\subsection{The Uniqueness Condition}

The main point is to show that two irreducible, I-O equivalent nets
must necessarily be the same net, up to some simple {\it internal
symmetries}. Clearly, if a net $N$ is reducible (using one or more of
the above three reducibility conditions), then it is I-O equivalent to
another net with fewer hidden nodes.
Some simple {\it internal symmetries} create various transformations
that can be applied to a network $N$ without changing its I-O map. 
These symmetries are:
\bi
\item
{\bf Sign-flipping}: Take a network $N$, pick a hidden 
node $j$ and change the sign of all the fan-in connection
weights $b_{ij}$ for $i=0,1,\ldots,m$, to node $j$, change the
sign of the fan-out connection weight $c_{jk}$ for $k=1,\ldots,u$, and
also change the sign of its threshold ($\theta_j$). 
Since $\sigma$ is odd, this will not alter the contribution of this
node $j$ to the output layer. Now let us call the resulting net
$\Upsilon_j (N)$.  
\item
{\bf Node permutation/interchange}: Using the same original net $N$, 
interchange two hidden nodes. That is, take two hidden nodes (in any
order), $j_1$ and $j_2$, and relabel $j_1$ as 
$j_2$ and $j_2$ as $j_1$, taking care to also relabel the
corresponding fan-in and fan-out weights and the two nodes thresholds.
(Via this interchange, consider a new net with weights $b_{ij}^{new}$,
$c_{jk}^{new}$, such  
that $b_{ij_1}^{new} = b_{ij_2}$, $b_{ij_2}^{new} = b_{ij_1}$, 
$c_{j_1k}^{new} = c_{j_2k}$, $c_{j_2k}^{new} = c_{j_1k}$, and
thresholds $\theta^{new}_{j_1}$, $\theta^{new}_{j_2}$, such that
$\theta^{new}_{j_1} = \theta_{j_2}$, and $\theta^{new}_{j_2} =
\theta_{j_1}$). Let us call the resulting net $\Phi_{j_1 j_2} (N)$. 
\ei
The maps $\Upsilon_j$, $\Phi_{j_1 j_2}$ generate a finite group 
${\cal G}_{m, n, u}$ of  transformations of the set 
${\cal N}_{m, n, u}$ of all nets with $m$ input nodes, $n$ hidden
nodes, and $u$ output units. We can call two nets in 
${\cal N}_{m, n, u}$ {\it equivalent} if they are related by a
transformation in the group ${\cal G}_{m, n, u}$. It is then clear
that two equivalent nets are I-O equivalent.   

Now, Sussmann's major result is:

\bt{Sussmann-main-result}
Let $N_1$, $N_2$ be irreducible I-O equivalent nets
in ${\cal N}_{m, n_1, u}$, ${\cal N}_{m, n_2, u}$, with $\sigma_h$ as
activation functions. 
Then (i) $n_1 = n_2$ and (ii) $N_1$ and $N_2$ are ${\cal
N}_{m,n,u}$-equivalent. 
\ets

This theorem implies the following corollary:

\bc{Sussmann-main-corollary}
An irreducible $\sigma_h$-net is minimal.
\ec

\section{Piecewise Rational Functions, Uniqueness, and Reducibility}

The class of piecewise rational functions is quite large, and for the
rest of the paper we will confine ourselves to two types of functions in
this class. Definitions of these two piecewise rational functions will
be carried out in this section. Also, from this section on we will
refer to the set of piecewise rational functions which are also smooth
activations (see definition \ref{def-of-smooth}) as ${\cal
PWR}$, and to networks using them as ${\cal PWR}$ nets. 

\subsection{Why are we interested in piecewise rational functions?}
Here are few reasons:
\begin{enumerate}
\item When properly set over intervals such as $(-1,1)$, piecewise
rational functions can approximate the function $tanh()$ over the same
interval. 
\item Evaluation of ${\cal PWR}$ functions may be much faster than
evaluation of $tanh()$. 
\item If training and convergence are not significantly worse for
${\cal PWR}$ nets then their overall training will be faster.
\item For sequential implementations, the time to evaluate $\sigma$ (the
activation function) and its first derivative, $\sigma^{'}$, may not
be very important in large networks; but parallel implementations can
be more sensitive to the effort required to evaluate $\sigma$ and
$\sigma^{'}$. Thus, we expect a faster parallel implementation when
${\cal PWR}$ functions are used as activation functions.
\end{enumerate}

\subsection{Definitions and Observations}

\bd{pwr-function}
For an integer $k > 0$, and real value $x_0 =  {k \over {k+1}}$, we define:
\be{pwr-form-1}
pwr_k(x) = 
 1.0 - {(1.0-x_0)x_0^k \over  {x^k}}\;,\;\;\;{\text{for} x \neq 0}\;.
\ee

The first ${\cal PWR}$ activation function used is:

\be{pwr-form-2}
\sigma_k(x) =
\threeif {-pwr_k(-x)} {\text{if} x  < -x_0}
         {pwr_k(x)} {\text{if} x > x_0}
         {x} {\text{otherwise.}}
\ee
\ed

\bo{pwr-func-derivative}
The first derivative of the function in (\ref{pwr-form-1}) is:
\be{pwr-deriv-1}
pwr^{'}_k(x) = 
 k {(1.0-x_0)x_0^k \over {x^{k+1}}} \; ,
\ee
and the second derivative is:
\be{pwr-deriv-2nd}
pwr^{''}_k(x) =
-k(k+1) {(1.0-x_0)x_0^k \over {x^{k+2}}} \; .
\ee

Now the first derivative of $\sigma_k(x)$ is:

\be{pwr-deriv-2}
\sigma^{'}_k(x) =
\twoif {pwr^{'}_k(|x|)} {\text{if} x < -x_0 \text{or} x_0 < x}
       {1} {\text{otherwise.}}
\ee
\eo

\bo{pwr-at-x0}
From previous definitions and observations, we observe the following:
\begin{itemize}
\item $pwr_k(x_0) = x_0\;$, and
\item 
$pwr^{'}_k(x_0) =$
$k {(1.0 - x_0)x_0^{k} \over x_0^{k+1}} =$
$k {(1.0 - x_0) \over x_0} =$
$k {{1.0 - {k \over (k+1)} (k+1)} \over k} = 1\;$.
\end{itemize}

Also we observe some properties of $\sigma_k$ that are shared with
$\tanh$: 
\begin{itemize}
\item For all $x$, $-1 \leq \sigma_k(x) \leq 1$ .
\item $\sigma_k$ is odd.
\item $\sigma_k$ and $\sigma^{'}_k$ are continuous.
\item For all $x$, $\sigma^{'}_k > 0$.
\item $\sigma_k(0) = 0$ and $\sigma^{'}_k(0) = 1$.
\end{itemize}
\eo

The second ${\cal PWR}$ function, due to Elliott \cite{9},
is defined next. 

\bd{pwr-function-type2}
\be{pwr.type2.1}
\sigma_p(x) = {x \over {1+|x|}}\; .
\ee
\ed

\bo{observe-pwr2-deriv}
The function stated in equation (\ref{pwr.type2.1})
is differentiable everywhere to:  
\be{observe-pwr2-deriv.1}
\sigma^{'}_p(x) = {1 \over {(1+|x|)^2}} \;\;,
\ee
and satisfies a ``general'' logistic differential equation as follows:
\be{pwr.type2.2}
\sigma^{'}_p = {(1.0 - |\sigma_p|)}^2\; .
\ee
\eo

\bo{pwr2-differentiation-steps}
The steps leading to equation (\ref{pwr.type2.2}) from function
(\ref{pwr.type2.1}) are as follows:

\be{step.1}
\text{Let}\;\;\;\;p_1(x) = 1 - {1 \over {1+x}} = {x \over {1+x}}\;\;
{\text{for} x \geq 0}\; , 
\ee
differentiating to:
\be{step.2}
{p_1}^{'}(x) = {{(1+x) - x} \over {(1+x)^2}} = {1 \over
{(1+x)^2}} = {1 \over {(1+|x|)^2}}\; ,
\ee
and a second derivative of:
\be{step.3}
{p_1}^{''}(x) = {-2 \over {(1+x)^3}}\; .
\ee
Also,
\be{step.4}
\text{let}\;\;\;\;{p_2}(x) = -1 + {1 \over {1-x}} = {x \over
{1-x}}\;\; {\text{for} x < 0}\; , 
\ee
differentiating to:
\be{step.5}
{p_2}^{'}(x) = {{(1-x) + x} \over {(1-x)^2}} = {1 \over
{(1-x)^2}} = {1 \over {(1+|x|)^2}}\; ,
\ee
and a second derivative of:
\be{step.6}
{p_2}^{''}(x) = {2 \over {(1-x)^3}}\; .
\ee

Now, from equations ($\ref{step.2}$, $\ref{step.5}$) we derive the
following:

\be{step.7}
{1 \over {(1+|x|)^2}} = {(|x| - |x| + 1)^2 \over {(1+|x|)^2}} = ({{|x|
+ 1} \over {|x| + 1}} - {|x| \over {1+|x|}})^2 = (1 - {|x| \over
{1+|x|}})^2 = (1 - |\sigma_p(x)|)^2\;\;.
\ee
\eo


\br{observe-function}
It is worth pointing out that $\sigma_p$ and $\sigma_h$ satisfy
an ``autonomous'' differential equation, so that calculating
$\sigma_p^{'}$ or $\sigma_k^{'}$ requires very little effort beyond
the calculation of the function itself. The aforementioned
``autonomy'' concept can be illustrated by the following example:

To evaluate functions $\sigma_h^{'} = 1 - \sigma_h^2$  and
$\sigma_p^{'} = (1 - |\sigma_p|)^2$, the only values needed are
$\sigma_h$ and $\sigma_p$, respectively.

Regarding the activation function $\sigma_k$, it seems not to satisfy
such a differential equation, but even so calculation of $\sigma_k^{'}$
requires negligible additional effort. Also, networks using these three
types of activation functions, can be trained using backpropogation
algorithm.
\er

\bo{observe-another-form}
We observe some properties of $\sigma_p$ shared with $\sigma_h$: 
\begin{itemize}
\item $\sigma_p$ and $\sigma^{'}_p$ are continuous.
\item For all $x$, $\sigma^{'}_p(x) > 0$.
\item $\sigma_p(0) = 0$ and $\sigma^{'}_p(0) = 1$.
\item $\sigma_p$ is odd.
\item For all $x$, $-1 \leq \sigma_p(x) \leq 1$.
\end{itemize}
\eo

%%%%%%%%%%%%%%%%% The following is in gnuplot.....
%%%
\begin{figure}[htb]
\centerline{\psfig{figure=figure9.ps,width=6in,angle=-90}}
\caption{f1() = $\sigma_1$, f2() = $\sigma_p$, and f3() = $\tanh()$.} 
\label{graph.1}
\end{figure}

%%\end{figure}             %%% this indicates that the above and
                           %%% the next plot are in the same page.

\subsubsection{On the continuity of the piecewise rational functions}

As in observation ($\ref{pwr-at-x0}$), when $x = x_0$, we obtain
$pwr^{'}_k(x_0) = 1$. From this and the $pwr^{'}_k(x)$ of equation
($\ref{pwr-deriv-1}$), we saw that the first derivative of function
$pwr_k(x)$ is continuous. 

Regarding the second derivative $pwr^{''}_k(x)$, at $x = x_0$, we
obtain the following derivation:
\be{cont.1}
pwr^{''}_k(x_0) =
-k(k+1) {(1.0-x_0) \over {x_0^2}} = -k(k+1) [{(k+1)^2 \over k^2} -
{(k+1) \over k}] = -{(k+1)^3 \over k} + (k+1)^2\;\;,
\ee
and 
\be{cont.1.1}
-{(k+1)^3 \over k} + (k+1)^2 = - {(k+1)^2 \over k} \neq 0\;\;,
\ee
which is not continuous. For a pictorial representation, see
Figure-($\ref{graph.2}$). 

On the issue of first and second derivatives continuity of the
function defined in equation ($\ref{pwr.type2.1}$), the first
derivative of equation ($\ref{step.2}$) is clearly continuous as well
as that of equation ($\ref{step.5}$). 

About the second derivatives of equations ($\ref{step.3}$ and
$\ref{step.6}$) we get the following:
\be{cont.4}
\text{At} x=0\;,\;\;\; {p_1}^{''}(0) = -2 \neq {p_2}^{''}(0) = 2\;\;. 
\ee
Therefore, as shown in Figure-($\ref{graph.3}$), the function's graph
is broken at $0$. Hence, $\sigma_{p}^{''}$ is not a continuous function.


\begin{figure}[htb]
\centerline{\psfig{figure=PwrPrimePrime.ps,width=6in,angle=-90}}
\caption{A plot showing the $2^{nd}$ derivative ($f^{''}$) of $pwr_k$
at $k=1$, which is $pwr^{''}_k\;$.} 
\label{graph.2}
\end{figure}

\begin{figure}[htb]
\centerline{\psfig{figure=Pwr2PrimePrime.ps,width=6in,angle=-90}}
\caption{A plot showing the $2^{nd}$ derivative ($f^{''}$) of
$\sigma_p$, which is $\sigma^{''}_p\;$.} 
\label{graph.3}
\end{figure}


\subsection{Network Equivalence and Uniqueness}
Let $N_1$ and $N_2$ stand for 2 feedforward nets, for example, see
Figure-\ref{fig.1}. Also, let the symbol ($\sim$) stands for
${\cal N}_{m, n, u}$-equivalence in behavior, and ($\equiv$) for
${\cal N}_{m, n, u}$-equivalence in structure. 

Albertini, Sontag and Maillot \cite{5} have stated
that given two networks $N_1$ and $N_2$, one says that they
are I-O equivalent if the behavior of $N_1$ equal to the behavior of
$N_2$. In other words, applying the same set of inputs to both
networks will yield the same output. Clearly, networks with identical
structures and identical internal representations ({\it weight sets})
have the same I-O mappings. Also, nets with different internal
representations can have the same I-O mappings.

Now, what we would like to answer is the following question: When does
$N_1 \sim N_2$ imply $N_1 \equiv N_2$ ? 

Sontag \cite{20} pointed out that Sussmann's
argument takes into account the ``independence property'' (IP)
(defined below), but he did not explicitly state this property in his
work \cite{8}. Also, they state that to show uniqueness of
the connection weights of a given network, one needs to demonstrate that
the given activation functions satisfy IP.
Sussmann showed that $\sigma_h$ and the related sigmoid $\sigma_s$
satisfy IP. 

\subsubsection{On the Independence Property}

\bd{the-independence-property}
A function $\sigma$ satisfies IP {\it if only if, for every
positive integer $l$, every set of non-zero real numbers $A =
\{a_1,\dots,a_l\}$, and every set of real numbers  
$B = \{b_1,\ldots,b_l\}$ which satisfy  
\be{IP.1}
\forall (i,j) \text{such that} i \neq j, \text{neither} (a_i,b_i) =
(a_j,b_j) \text{nor} (a_i,b_i) = (-a_j, -b_j) \;\;,
\ee
the functions:
\be{IP.2}
\mu_0(u) = 1, \mu_1(u) = \sigma(a_1 u + b_1),\ldots, \mu_l(u) =
\sigma(a_l u + b_l) 
\ee
are linearly independent}. This linear independence means that unless
\be{coeff}
c_0 = c_1 = c_2 = \ldots = c_l = 0 \;,
\ee
it must be that, for some $u$ :
\be{lin-ind-equation}
c_0 + c_1  \sigma(a_1 u + b_1) + \ldots + c_l  \sigma(a_l u + b_l) \neq 0\;.
\ee
Elements of equation ($\ref{IP.2}$) are of the linear space
(over ${\cal R}$), consisting of all functions defined on ${\cal R}$ :
\be{linear-space-elements}
(c_0 \mu_0 + c_1 \mu_1 +\ldots + c_l \mu_l) (x) = c_0 \mu_0(x) +
\ldots + c_l \mu_l(x) \;.
\ee
Otherwise, they are linearly dependent and one of them can be formed
as a linear combination of the others.
\ed

In addition,  $\sigma$ satisfies the {\bf Weak Independence Property}
(WIP), if the above IP is only required to hold  for all pairs with
$b_i= 0, i=1,\ldots,l$.  

There are many nonlinear maps that do not satisfy IP. An example of
functions that belongs to this category are {\bf polynomials}, {\bf
periodic functions}, and the {\bf exponential function}
\cite{4}. 

\subsubsection{Uniqueness and the Independence Property}

\bo{irreducible}
Albertini, Sontag and Maillot \cite{4} observe that in fact
Sussmann showed the following: 

If $N_1$ and $N_2$ are irreducible nets with activation $\sigma$ and
(i) $N_1 \sim N_2$, (ii) $\sigma$ is odd, and (iii) $\sigma$ satisfies
IP, then $n_1 = n_2$  and $N_1 \equiv N_2$ (see Theorem
\ref{Sussmann-main-result}).
\eo

\subsubsection{The Independence Property and Piecewise Rational Functions}

Assume our network uses ${\cal PWR}$ functions (see definitions
\ref{pwr-function} and \ref{pwr-function-type2}) as the activations of
the nodes. Now, we need to address the issue of whether 
these types of activation functions satisfy the $IP$. 

{\bf First}: Assume the activation function is $\sigma_k$.

Choose an integer $l > 0$, non-zero real numbers $a_1,\ldots, a_l$
and real numbers $b_1,\ldots,b_l$.
\be{equa.1}
\sigma_k(a_i x + b_i) = a_i x + b_i\;\;\;\text{if}\;|a_i x + b_i|
\leq x_0\;,
\ee
otherwise
\be{equa.2}
\sigma_k(a_i x + b_i) = sgn(a_i x + b_i)(1 - {{(1-x_0)x_0^k} \over {(|a_i x +
b_i|)^k}})\;\;.
\ee
Select a set of coefficients $C = \{c_0,\ldots,c_l\}$. We need to show:
\be{equa.3}
c_0 + \sum_{i=1}^l c_i \sigma_k(a_i x + b_i)\neq 0\;\;\;\text{for
some}\; x\;.
\ee

By confining one's attention to $x$ for which $|x|$ is sufficiently
large that $|a_i x + b_i| > x_0$, for all $i$, one can see that it is
sufficient to show that $pwr_k$ satisfies IP. A sketch of the proof
follows:

{\bf \underline{Proof}}

We show by {\bf contradiction} that $pwr_k$ satisfies the IP. 
Assume any reference to $\sigma$ is a reference to $\sigma_k$.

{\bf [1]}: $\;$ $\sigma$ is $C^{\infty}$ on $|x| < x_0$, and
$|x| > x_0$.

Let $\sigma^{(n)}$ to be the $n^{th}$ derivative of $\sigma$. Also
note that:

\be{pe1}
\;\;\;\;\;\;\; \sigma_{-}^{(n)} (x_0) = \lim_{x \rightarrow x_0^{-}}
\sigma^{(n)}(x_0) 
\ee

\be{pe2}
\;\;\;\;\;\;\; \sigma_{+}^{(n)} (x_0) = \lim_{x \rightarrow x_0^{+}}
\sigma^{(n)}(x_0) 
\ee

Let $\Delta_n$ = $\sigma_{+}^{(n)} (x_0) - \sigma_{-}^{(n)} (x_0)
\;\;\;$ for $n \in {\cal N}^{*}$.

By straightforward calculations, for $n \geq 2$, we get:

\be{pe3}
\;\;\;\;\;\;\; \sigma_{-}^{(n)} (x_0) = 0
\ee

\be{pe4}
\;\;\;\;\;\;\; \sigma_{+}^{(n)} = {(-1)}^{n+1} {{(k+n-1)!} \over
  {(k-1)!}} \cdot {(1 - x_0) \over {x_0}^n}
\ee

Therefore,

\be{pe5}
\;\;\;\;\;\;\; \Delta_n = {(-1)}^{n+1} {{(k+n-1)!} \over {(k-1)!}}
\cdot {(1 - x_0) \over {x_0}^n} \neq 0
\ee

(The main point here is that $\Delta_n \neq 0$ for $n \geq 2$, of
course $\Delta_0 = 0$ and $\Delta_1 = 0$ because of the continuity of
$\sigma$ and $\sigma^{'}$).

{\bf [2]}: $\;$ Now suppose there exist: 

$(c_0, c_1, \ldots, c_{l} \in {\cal R}^{*})$
and 
$(b_1, b_2, \ldots, b_{l} \in {\cal R}^{*})$
and 
$(B_1, B_2, \ldots, B_{l} \in {\cal R})$

such that:

\be{pe6}
\;\;\;\;\;\;\; (b_i, B_i) \neq \pm (b_j, B_j) \;\;\;\; \forall i\neq j
\ee

and 
\be{pe7}
\;\;\;\;\;\;\; c_0 + \sum_{i=1}^l c_i \sigma(b_i x + B_i) = 0
\;\;\;\; (\forall x \in {\cal R})
\ee

Changing the sign of some of the $c_i$, we also can assume all the
$b_i > 0$. 

(This assumption is not actually necessary but more
convenient for the proof).

Now, let $x_1 \in {\cal R}$ be the {\it largest} $x \in {\cal R}$ such
that for one of the $b_i$, we have:

$x \longmapsto \sigma (b_i x + B_i)$ is not $C^{\infty}$ at
$x_1$. This means that  $b_i x_1 + B_i = x_0$ because $b_i > 0$.

Consider all the $b_j$ such that: 
$x \longmapsto \sigma (b_j x + B_j)$ is not $C^{\infty}$ at $x_1$.

Rearranging the $b_j$, we can denote them by $b_1, \ldots, b_p$ for $p
\leq l$.  Consider the function:

\be{pe8}
\;\;\;\;\;\;\; \Theta (x) + \sum_{i=p+1}^l c_i \sigma(b_i x + B_i) =
- c_0
\ee

We get that $\Theta$ is $C^{\infty}$ at $x_1$.
Of course, we must have $p > 1$. Now, for $x$ near $x_1$, but with $x
\neq x_1$, we get:

\be{pe9}
\;\;\;\;\;\;\; \Theta^{(n)} (x) = \sum_{i=1}^p c_i b_i^{n}
\sigma^{(n)} (b_i x + B_i)
\ee
and because $\Theta$ is $C^{\infty}$ at $x_1$,

\be{pe10}
\;\;\;\;\;\;\; \lim_{x \rightarrow x_1^{-}} \Theta^{(n)}(x) = \lim_{x
  \rightarrow x_1^{+}} \Theta^{(n)}(x)
\ee

So, because:

\be{pe11}
\;\;\;\;\;\;\; \lim_{x \rightarrow x_1^{-}} \sigma^{(n)} (b_i x + B_i)
= \sigma_{-}^{(n)} (x_0)
\ee

\be{pe12} 
\;\;\;\;\;\;\; \lim_{x \rightarrow x_1^{+}} \sigma^{(n)} (b_i x + B_i)
= \sigma_{+}^{(n)} (x_0)
\ee

(Remember that $b_i x_1 + B_i = x_0$). Now, we get:

\be{pe13}
\;\;\;\;\;\;\; \left(\sum_{i=1}^{p} c_i
  b_i^{n}\right)\left[\sigma_{+}^{(n)} (x_0) - \sigma_{-}^{(n)}
  (x_0)\right] = 0
\ee

$\Longrightarrow \left(\sum_{i=1}^{p} c_i
  b_i^{n}\right) \Delta_n = 0$.

Then, we choose $n \geq 2$, and $\Delta_n \neq 0$, 
$\;\;\Longrightarrow \sum_{i=1}^{p} c_i b_i^{n} = 0 \;\;\;
\forall n \geq 2$ .

Considering this quality for $2\leq n \leq (p + 2)$, we get:

\be{pe14}
\left(\begin{array}{lll} b_1^2 & \ldots & b_p^2\\
\ldots & \ldots & \ldots\\
b_1^{p+2} & \ldots & b_p^{p+2}\end{array}\right)\left(\begin{array}{l}
c_1\\
\ldots\\
c_p\end{array}\right) = 0
\ee

Now, the $c_i \neq 0$, we can conclude that:

\be{pe15}
\det\left|\begin{array}{lll} b_1^2 & \ldots & b_p^2\\
\ldots & \ldots & \ldots\\
b_1^{p+2} & \ldots & b_p^{p+2}\end{array}\right| = 0
\ee

$\Longrightarrow {(b_1 - b_p)}^2 \prod_{1\leq i < j \leq p} (b_i -
b_j) = 0$, because the $b_i > 0$, we obtain:

\be{pe16}
\prod_{1\leq i < j \leq p} (b_i - b_j) = 0
\ee

This means that we can find $i$ and $j$ such that: $i\neq j$ and $b_i
= b_j$. But,

\be{pe17}
b_i x_1 + B_i = x_0 = b_j x_1 + B_j
\ee

Then $B_i = B_j$, hence, we get:
$i\neq j$ and $(b_i,B_i) = (b_j, B_j)$.

Which is a clear contradiction. $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\bf QED}$.
\vspace{0.45in}

Certainly the above model (and reasoning) can be applied in more
general situations. For example, whenever we consider piecewise
rational functions, (because such a type of functions cannot be
$C^{\infty}$ on ${\cal R}$. Now, the theorem becomes:

\bt{new-theorem}
Let $f$ be an odd or even piecewise rational function, then $f$ has
(or satisfies) the strong I.P. property.
\et

Anyway, the odd or even hypothesis is kind of strong, and taking care
of what one needs to do, it is possible to prove the same theorem for
``almost'' piecewise rational functions.



%%%% We conjecture the
%%%% $pwr_k$ satisfies IP but have not shown it.

{\bf Second}: Let the activation function be $\sigma_p$.
Sontag \cite{20} communicated to me that $\sigma_p$ 
satisfies the independence property.

Clearly, networks using $\sigma_p$, and assuming the above conjecture,
networks using $\sigma_k$, satisfy the property that 
if $N_1$ and $N_2$ are irreducible in ${\cal N}_{m,n,u}$ and 
the $N_1 \sim N_2$ then $N_1 \equiv N_2$.  


\section{Piecewise Linear Nets}

\subsection{Why are we interested in them?}

\begin{enumerate}

\item Piecewise linear functions (${\cal PLF}$) are simple to evaluate.

\item Smooth activation functions, such as $\sigma$ of the previous
section, were originally introduced as smooth versions of certain
piecewise linear activation functions (in this case, the clipping
type). 

\item Clipping plays a quite useful role as outlined 
recently by Hertz et. al \cite{11} (see the section on
discretization and clipping).

\item It is stated in Sontag's work\cite{15} that the
conventional squashing function (see previous section) as well as the
${\cal PLF}$ satisfy the criteria of continuity and differentiability
almost everywhere (see conditions $S_1$ and $S_2$ of definition 3.2 in
\cite{15}). 

\end{enumerate}

\subsection{Definitions and Observations}

\bd{PL-func-dfn} (see \cite{12})
A function $\varphi$ on the interval $[a,b]$ is a piecewise linear
(${\cal PLF}$) 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}]$,
for $0\leq i < n$.   
\ed

In this paper, we only consider the class of ${\cal PLF}$ that meets
the continuity criteria. This class will be referred to as the {\it
clipping} type or the {\it clip} functions.

\bd{clip-func-dfn}
The {\it clip} function ($clip$) is  of one of the following two
forms: 
\be{clip-form-1}
clip_0(x) =
\threeif {0} {\text{if} x  \leq  0}
         {x} {\text{if} 0 < x < 1}
         {1} {\text{if} x \geq 1}
\ee
\be{clip-form-2}
clip_1(x) =
\threeif {-1} {\text{if} x  \leq  -1}
         {x} {\text{if} -1 < x < 1}
         {1} {\text{if} x \geq 1}
\ee
\ed

\bo{ob-clip.1}
The relationship between $clip_0$ and $clip_1$ is:
\be{clip-1-2-relation}
clip_1(x) = 2\;\cdot\;clip_0 ({{x+1} \over {2}} ) - 1
\ee
\eo

From this point on, any reference to {\bf $clip$} is intended to refer
to {\it $clip_1$}. 

\bd{PL-net-dfn}
A piecewise linear network (${\cal PLN}$) is a feedforward multilayer
net using ${\cal PLF}$ as activation functions.
\ed

\subsection{Examples}

The following example shows a network in which the concepts
of irreducibility and uniqueness do not hold. Again, the hidden and
output layers of Figure-\ref{fig.8}(a) are composed of {\it clip}
functions. Clearly $n$ has a value greater than $1$, hence
$clip(n) = 1$.

Now, the net of Figure-\ref{fig.8}(a) has the following output:
\be{example.2.1}
y_1 = clip({1 \over n} clip(n\;\cdot\;x) + {1 \over n}
clip(n\;\cdot\;x) + \ldots + {1 \over n} clip(n\;\cdot\;x) + clip(x)),
\ee

\be{example.2.2}
= clip({{n-1} \over n} clip (n\;\cdot\;x) + clip(x)),
\ee
\be{example.2.3}
= clip({{n-1} \over n} clip(n)\;\cdot\;clip(x) + clip(x)),
\ee
\be{example.2.4}
= clip({{n-1} \over n} clip(x) + clip(x)),
\ee
\be{example.2.5}
= clip((1 + {{n-1} \over n}) clip(x)),
\ee
\be{example.2.6}
= {{clip(2 n -1)} \over clip(n)} clip(clip(x)).
\ee
Since $n > 1$ we get $(2 n -1) > 1$, thus $clip(2 n -1) = 1\;$.
\be{example.2.7}
y_1 = clip(clip(x)),
\ee
\be{example.2.8}
= clip(x)\;.
\ee

The net of Figure-\ref{fig.8}(b) gives an output of:

\be{example.2.9}
y_2 = clip(n \;\cdot\;clip(1\;\cdot\;x)) =
clip(n)\;\cdot\;clip(clip(x)) = clip(x)\;.
\ee
While the output of Figure-\ref{fig.8}(c) net is:
\be{example.2.10}
y_3 = clip(1\;\cdot\;clip(n\;\cdot\;x)) = clip(clip(n\;\cdot\;x)) =
clip(clip(n)\;\cdot\;clip(x)),
\ee
\be{example.2.11}
 = clip(clip(x)) = clip(x)\;.
\ee

\begin{figure}
\postscript{figure8.ps}{0.80}
\caption{Three piecewise linear nets.}
\label{fig.8}
\end{figure}


Since $y_1 = y_2 = y_3$, the three networks are I-O equivalent.
Clearly, the nets are not structurely equivalent, which contradicts
the concepts of irreducibility and uniqueness discussed in the last
section. Hence, piecewise linear nets using $clip$ activation
functions, do not satisfy the properties of irreducibility and
uniqueness.


\section{Experimental Results for Piecewise Rational Nets}

Using the Aspirin/MIGRAINES \cite{3} software system, a
neural net example is used to show the evaluation time of $\sigma_k$
and $\sigma_p$.  
First, we substituted $\sigma_k$ for $\sigma_h$ (the net's default
activation function), then ran it on the problem and recorded the
results. Next, $\sigma_p$ is used in place of $\sigma_k$ and the results
were also recorded. These two sets of results are
compared with those obtained from running the network on the same
problem using $\sigma_h$. 

\subsection{The Spiral Problem}

Briefly, this is an example of a very hard pattern recognition
problem. The data are the $x$ and $y$ coordinates of two spirals. In
the actual data file the coordinates for each spiral have an
additional number associated with them which denotes to which spiral
the coordinate belongs to (i.e., 1.0 for one spiral and -1.0 for the
other). The two spirals coil three times around the origin and around
one another. The goal of this example is to train the network to map
an $(x,y)$ coordinate into the proper spiral. The network is trained
by giving it $x$ and $y$ and the target classification for some of the
points along these intertwined spirals. For a detailed description of
this problem, see Lang and Withbrock \cite{1}. 

\subsection{The Experiment} 

\subsubsection{Problem Description}
Two sets of points are generated, each with 97
members (three complete revolutions at 32 points per revolution, plus
endpoints). Each point is represented by two floating-point numbers,
the $x$ and $y$ coordinates, plus an output value of $-1.0$ for one
set, $+1.0$ for the other set.

\subsubsection{Methodology}
The task is to train on the 194 (97 x 2) I/O pairs
until the learning system can produce the correct output for all of
the inputs. The time required for learning is then recorded. For
back-propagation systems, the time is typically recorded in
``epochs''. Each epoch includes one training presentation for each of
the 194 points in the training set. An output is considered to be a
logical -1 if it is in the lower $40\%$ of the output range, a +1 if
it is in the upper $40\%$, and indeterminate (and therefore incorrect)
if it is in the middle $20\%$ of the range.

\subsubsection{Results}
Lang and Withbrock \cite{1} report results obtained on this
problem using $2\rightarrow 5\rightarrow 5\rightarrow 5\rightarrow 1$ 
(a two-node input layer, five-node first hidden layer, five-node
second hidden layer, five-node third hidden layer, and one-node output
layer) network with short-cut connections (each unit is connected to
every unit in all earlier layers, not just to units in the previous layer).
For this experiment, we use a $2\rightarrow 5\rightarrow 10\rightarrow
15\rightarrow 1$ network with also short-cut connections.

In the three runs of the network over the same input data, the first
run uses $\sigma_h$, the second uses $\sigma_1$, and the third uses
$\sigma_p$ activation functions. For each run, the network weights are
initialized with a uniformly distributed random values in the range
$-0.1$ to $+0.1$. Learning rate and momentum are set at $0.1$ and
$0.95$, respectively. The error bound is set to $0.4$. The network is
periodically (every 100000 iterations) saved to a file.
Table-(\ref{table.1}) summarizes the various testing and learning
times. Note that the elapsed compute and system times are measured in
{\em seconds}, and average performance on the task is measured in
{\em connections per second}.

\smallskip
\begin{table}
$$
\begin{tabular}{|l||c|c||c|c||c|c|}
\hline
                 &\multicolumn{2}{|c|}{Using
$\sigma_h$}&\multicolumn{2}{|c|}{Using
$\sigma_1$}&\multicolumn{2}{|c|}{Using $\sigma_p$}\\ \hline\hline
                 & Learning & Testing  & Learning & Testing & Learning
& Testing\\ \hline\hline
Elapsed     & 916.75 & 1.2400 & 579.70 & 1.7000 & 1967.0 & 1.4000\\
Compute     &        &        &        &        &        &\\       
Time        &        &        &        &        &        &\\ \hline
Elapsed     & 1.4800 & 0.2100 & 0.3500 & 0.2200 & 0.9400 & 0.1800\\ 
System      &        &        &        &        &        &\\ 
Time        &        &        &        &        &        &\\ \hline
Avg.        & 86828.5 & 62267.7 & 171827 & 72160.7 & 171988 & 74242.3\\
Performance &        &        &        &        &           &\\
on the task &        &        &        &        &           &\\ \hline
Total       & 200000 & 194    & 250000 & 194    & 850000  & 194\\ 
iterations  &        &        &        &        &         &\\ \hline
Total       & 1030.93 & 1.000 & 1288.66 & 1.000 & 4381.44 & 1.000\\ 
epochs      &        &        &        &        &         &\\ \hline
Total       & 398    & 398    & 398    & 398    & 398     & 398\\
number of   &        &        &        &        &         &\\
connection  &        &        &        &        &         &\\ \hline 
\end{tabular}
$$
\caption{Performance Figures for Spirals}
\label{table.1}
\end{table}


\section{Conclusion}

We have looked at the issues of reducibility and uniqueness,
pertaining to feedforward neural nets, introduced by Hector Sussmann
to analyze nets composed of $\tanh()$ units. In the course of this 
analysis, two types of piecewise rational functions and one type of
piecewise linear activation have been examined to determine whether
they satisfy the above two issues. 
Our results show that neither reducibility nor uniqueness holds when
the functions involved are piecewise linear (the {\it clip} type
functions), but they do hold when piecewise rational activations are
used. 

\section*{Acknowledgment}
Many thanks to Ernie Sibert, for his useful comments and suggestions
while writing this report. Also, would like to thank Paul Coddington
and Geoffrey Fox for their support.


\clearpage
%\newpage
\begin{thebibliography}{SE}

\bibitem{5}
Albertini, F., E. Sontag, and V. Maillot,
``For Neural Nets, Function Determines Form'', Rutgers Center for
Systems and Control, report SYSCON-92-03. 1992.

\bibitem{4}
Albertini, F., E. Sontag, and V. Maillot,
``Uniqueness of weights for neural networks'', in {\it Artificial
Neural Networks with Applications in Speech and Vision}, edited by R.
Mammone, Chapman and Hall, London, 1993.

\bibitem{6}
Chester, Dan,
{\it DIMACS Neural Nets Workshop presentation}, May 1991.

\bibitem{7}
Chester, Dan,
``The generalization capabilities of feedforward neural nets'',
Unpublished Draft.

\bibitem{22}
Chester, Dan, private communication.

\bibitem{13}
Cybenko, George,
``Continuous valued neural networks with two hidden layers are sufficient,''
CSRD-935, Univ. of Illinois, Urbana,IL (March 1988).

\bibitem{14}
Cybenko, George,
``Complexity Theory of Neural Networks and Classification Problems,''
Univ. of Illinois, Urbana, IL (April 1990).

\bibitem{9}
Elliot, David L.
``A Better Activation Function for Artificial Neural Networks'', 
TR 93-8, Institute for Systems Research, University of
Maryland, College Park, MD 20742, January 1993.

\bibitem{19}
Elliot, David, private communication.

\bibitem{10}
Hecht-Nielsen, Robert
``Theory of Backprop neural nets'',in  proc. of Int. Joint Conf. on
Neural Networks, Washington, 1989, IEEE Publications, NY, pp. 593-605.

\bibitem{11}
Hertz, John, Andres Krogh, and Richard Palmer,
{\it Intro. to the theory of neural computation}, Addison-Wesley,
Redwood City, 1991. 

\bibitem{1}
Lang, Kevin, and Michael Withbrock,
``Learning To Tell Two Spirals Apart'', in the proceedings of the 1988
Connectionists Summer School, Morgan Kaufmann (San Mateo, 1988).

\bibitem{3}
Leighton, Russell,
The Aspirin/MIGRAINES Neural Network Software system. Release V6.0,
the Mitre Corp. 1992.

\bibitem{21}
Maillot, V, private communication.

\bibitem{17}
Minsky, M and S. Papert, {\it Perceptron} , MIT Press, Cambridge, MA (1988 edition)

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

\bibitem{2}
Rumelhart, D , J McClelland, and the PDP Research Group.
Parallel Distributed Processing: Explorations in the Microstructure of
Cognition. Vol I, 1986. MIT Press, Cambridge.

\bibitem{15}
Sontag, E,
``Feedforward nets for interpolation and classification,'' SYCON Report,
Rutgers Univ., 1991.

\bibitem{16}
Sontag, E,
``Feedback stabilization using two-hidden-layer nets,'' IEEE
Trans. Neural Nets 3 (1992): 981-990.

\bibitem{20}
Sontag, E, private communication.

\bibitem{18}
Sussmann, Sontag, and Kuhn, (editors)
Proceedings of the DIMACS workshop on theoretical neural nets. May 1991.

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

\end{thebibliography}

\end{document}








