Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!network!sdcsvax!beowulf!heirich
From: heirich@beowulf.ucsd.edu (Alan Heirich)
Newsgroups: comp.ai.neural-nets
Subject: Re: Re : Step Function
Message-ID: <6980@sdcsvax.UCSD.Edu>
Date: 24 Aug 89 03:18:10 GMT
References: <1060@rex.cs.tulane.edu>
Sender: nobody@sdcsvax.UCSD.Edu
Reply-To: heirich@beowulf.UCSD.EDU (Alan Heirich)
Organization: EE/CS Dept. U.C. San Diego
Lines: 27

In article <1060@rex.cs.tulane.edu> ck@rex.cs.tulane.edu (Cris Koutsougeras) writes:
>With the back prop only an analytic (continous differentiable) can be learned.
>The perfect step function is not therefore it will not be learned. A close
>approximation can be learned if your training set has enough samples around
>the point of the jump and of course quite enough coverage of the rest of the
>total interval. Look at it from an other point of view. No matter how many 
>units (nodes) you put in your net, you are never going to have enough 
>non-linearity to match the perfect step function. If you want I can send you
>a paper on some related experiments from our group at Tulane U.

This statement makes me uncomfortable.  It has been proven (White) that a
two-layer feed forward network with a signmoid activation function (such as
you find in standard back propagation networks) can approximate any Borel
measurable function to an arbitrary degree of precision.  So, for all
intents and purposes, such a network can match a perfect step function to
any discernible precision.  On the other hand, I have not seen any literature
proving bounds on learnability.  This is obviously a very important area,
but if people are still quibbling about the prevelance of local minima in
error landscapes, I can't imagine that anyone has proven such a result about
which functions are learnable!

-------------------------
Alan Heirich     Comp. Sci. & Eng., Cognitive Science
C-014 University of California, San Diego 92093

heirich@cs.ucsd.edu
aheirich@ucsd.bitnet