Path: utzoo!attcan!uunet!lll-winken!ames!sun-barr!rutgers!att!cbnewsl!apr
From: apr@cbnewsl.ATT.COM (anthony.p.russo)
Newsgroups: comp.ai.neural-nets
Subject: Re: : Step Function
Summary: learnability
Message-ID: <1602@cbnewsl.ATT.COM>
Date: 24 Aug 89 13:43:32 GMT
References: <1060@rex.cs.tulane.edu> <6980@sdcsvax.UCSD.Edu>
Organization: AT&T Bell Laboratories
Lines: 24

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,
> 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.
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.
Perhaps not by backprop ...

There is, happily, a small body of research in this area, but not nearly
enough. the best reference I can give is:

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

	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	~  	 Tony Russo		" Surrender to the void."	~
	~  AT&T Bell Laboratories					~
	~   apr@cbnewsl.ATT.COM						~
	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~