Path: utzoo!utgpu!watmath!att!ucbvax!tut.cis.ohio-state.edu!pt.cs.cmu.edu!andrew.cmu.edu!dg1v+ From: dg1v+@andrew.cmu.edu (David Greene) Newsgroups: comp.ai.neural-nets Subject: Re: : Step Function Message-ID: Date: 30 Aug 89 17:07:35 GMT References: <1060@rex.cs.tulane.edu> <6980@sdcsvax.UCSD.Edu> <17522@bellcore.bellcore.com>, <1683@cbnewsl.ATT.COM> Organization: Graduate School of Industrial Administration, Carnegie Mellon, Pittsburgh, PA Lines: 32 In-Reply-To: <1683@cbnewsl.ATT.COM> > Excerpts from netnews.comp.ai.neural-nets: 30-Aug-89 Re: : Step Function > anthony.p.russo@cbnewsl. (1967) > 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*. I believe you are confusing 'sample' with 'census'. If the total population of examples is 100 (and assuming no noise) then perhaps your statement would be appropriate. However if the 100 represents a sample, then the issue of learnability after 99 examples from that sample is dependent on the size of the total population and the degree of confidence you require. (eg. Valient's PAC model of learnability -- Valient, L. G "A Theory of the Learnable" Communications of the ACM, 27 (11) :1134-1142, November 1984) -David -------------------------------------------------------------------- David Perry Greene || ARPA: dg1v@andrew.cmu.edu GSIA /Robotics || dpg@isl1.ri.cmu.edu Carnegie Mellon Univ. || BITNET: dg1v%andrew@vb.cc.cmu.edu Pittsburgh, PA 15213 || UUCP: !harvard!andrew.cmu.edu!dg1v -------------------------------------------------------------------- "You're welcome to use my opinions, just don't get them all wrinkled."