Path: utzoo!attcan!uunet!cs.utexas.edu!tut.cis.ohio-state.edu!network!sdcsvax!beowulf!demers
From: demers@beowulf.ucsd.edu (David E Demers)
Newsgroups: comp.ai.neural-nets
Subject: Re: : Step Function
Message-ID: <6981@sdcsvax.UCSD.Edu>
Date: 25 Aug 89 04:39:32 GMT
References: <1060@rex.cs.tulane.edu> <6980@sdcsvax.UCSD.Edu> <1602@cbnewsl.ATT.COM>
Sender: nobody@sdcsvax.UCSD.Edu
Reply-To: demers@beowulf.UCSD.EDU (David E Demers)
Organization: EE/CS Dept. U.C. San Diego
Lines: 56

In article <1602@cbnewsl.ATT.COM> apr@cbnewsl.ATT.COM (anthony.p.russo) writes:
>In article <6980@sdcsvax.UCSD.Edu>, heirich@beowulf.ucsd.edu (Alan Heirich) writes:
>> [...] I have not seen any literature
>> proving bounds on learnability.  This is obviously a very important area,
				^  I think Alan may mean "learnability
of the step function." here. 

>> 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!

>Some things have been proven not to be learnable, i.e. EX-OR.

Surely you jest.  XOR is not learnable by a neural net with
no hidden layers, but is certainly a learnable function.

>On the other hand, I'm sure no one has proven whether step-function
>scaling is learnable or not, but intuitively it seems that it is.
[...] the best reference I can give is:

>L.G. Valiant, "A theory of the Learnable," Communications of the ACM,
>vol. 27, no.11, 1984.

Also interesting are:
Ehrenfeucht, Haussler, Kearns & Valiant, "A General Lower Bound on
the Number of Examples Needed for Learning" appearing in Information
and Computation, 1988 [I just have a preprint...]

and
Haussler, "Quantifying Inductive Bias: AI Learning Algorithms and
Valiant's Learning Framework", Artificial Intelligence 36 (1988).

The proceedings of the 1988 workshop on Computational Learning
Theory are available from Morgan Kaufman.  One of my summer
projects was to read several of the papers from the workshop...
maybe at Christmas...

But back to the original subject -

I think Alan Heirich is right that the step function may be
APPROXIMATED to arbitrary precision by a net with one hidden
layer and sigmoid transfer functions.  Backpropogation may not
be an adequate learning method; however the cited work by
White (appearing in the current issue of Neural Networks, I
believe { vol 2 no. 3}) shows that the function IS learnable.
This is stronger than showing that a net can approximate it.

So, given the function and given a bound on the error, there
is a net which can approximate the function to that bound, and
an algorithm to learn the mapping.  Our job is to discover them :-)

Dave DeMers
demers@cs.ucsd.edu
Dept. of Computer Science  & Engineering
UCSD
La Jolla, CA 92093