Path: utzoo!utgpu!watmath!att!dptg!rutgers!usc!henry.jpl.nasa.gov!elroy.jpl.nasa.gov!news
From: mathew@jane.Jpl.Nasa.Gov (Mathew Yeates)
Newsgroups: comp.ai.neural-nets
Subject: Re: : Step Function
Keywords: learning,generalization
Message-ID: <1989Aug30.162345.9569@elroy.jpl.nasa.gov>
Date: 30 Aug 89 16:23:45 GMT
References: <1060@rex.cs.tulane.edu> <6980@sdcsvax.UCSD.Edu> <17522@bellcore.bellcore.com> <1683@cbnewsl.ATT.COM>
Reply-To: mathew@jane.Jpl.Nasa.Gov (Mathew Yeates)
Organization: Image Analysis Systems Grp, JPL
Lines: 14

>Perhaps our definitions of "learnable" are different. Mine is that,
>with a fraction of the possible samples, one can generalize to 100%
>accuracy. Otherwise, cfor example, if after 99 of 100 samples 
>one cannot correctly predict the last output 
>with 100% confidence, nothing has been learned
>at all about the function in question. If it does take 100% of the
>possibilities to learn something, that I claim it has not been learned,
>but rather *memorized*.

under this definition, no function is learnable. Considering a function as
a set of ordered pairs, seeing some subset of the ordered pairs can
never lead to a complete knowledge of the entire set. At least for
a mere  mortal. A rigorous definition of learnabilty from examples can
be found in Valiants "A Theory of the Learnable".