Xref: utzoo comp.ai.neural-nets:321 comp.ai:2620
Path: utzoo!attcan!uunet!husc6!ogccse!blake!uw-beaver!cornell!batcomputer!itsgw!nyser!njin!rutgers!bellcore!faline!sword!gamma!pyuxp!nvuxj!nvuxl!nvuxh!hall
From: hall@nvuxh.UUCP (Michael R Hall)
Newsgroups: comp.ai.neural-nets,comp.ai
Subject: Re: Learning arbitrary transfer functions
Message-ID: <282@nvuxh.UUCP>
Date: 16 Nov 88 21:04:58 GMT
References: <399@uvaee.ee.virginia.EDU>
Reply-To: hall@nvuxh.UUCP (23431-Michael R Hall)
Organization: Bell Communications Research
Lines: 48

In article <399@uvaee.ee.virginia.EDU> aam9n@uvaee.ee.virginia.EDU (Ali Minai) writes:
>I am looking for any references that might deal with the following
>problem:
>
>y = f(x);         f(x) is nonlinear in x
>
>Training Data = {(x1, y1), (x2, y2), ...... , (xn, yn)}
>
>Can the network now produce ym given xm, even if it has never seen the
>pair before?
>
>That is, given a set of input/output pairs for a nonlinear function, can a
>multi-layer neural network be trained to induce the transfer function
>by being shown the data? What are the network requirements? What
>are the limitations, if any? Are there theoretical bounds on
>the order, degree or complexity of learnable functions for networks
>of a given type?
>
>Note that I am speaking here of *continuous* functions, not discrete-valued
>ones, so there is no immediate congruence with classification. 

The problem you raise is not just a neural net problem.  Your
function learning problem has been termed "concept learning" by
some researchers (e.g. Larry Rendell).  A concept is a function. 
There are many nonneural learning algorithms (e.g. PLS1) that are
designed to learn concepts.  My opinion is that concept learning
algorithms generally work better, easier, and faster than neural
nets for learning concepts.  (Anybody willing to pit their neural
net against my implementation of PLS to learn a concept from natural
data?)  Neural nets are more general than concept learning
algorithms, and so it is only natural that they should not learn
concepts as quickly (in terms of exposures) and well (in terms of
accuracy after a given number of exposures).

Valiant and friends have come up with theories of the sort you
desire, but only for boolean concepts (binary y's in your notation)
and learning algorithms in general, not neural nets in particular.
"Graded concepts" are continuous.  To my knowledge, no work has
addressed the theoretical learnability of graded concepts.  Before
trying to come up with theoretical learnability results for neural
networks, one should probably address the graded concept learning
problem in general.  The Valiant approach of a Probably Almost
Correct (PAC) learning criterion should be applicable to graded
concepts. 
-- 
Michael R. Hall                               | Bell Communications Research
"I'm just a symptom of the moral decay that's | hall%nvuxh.UUCP@bellcore.COM
gnawing at the heart of the country" -The The | bellcore!nvuxh!hall