Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!bellcore!att!cbnewsl!apr
From: apr@cbnewsl.ATT.COM (anthony.p.russo)
Newsgroups: comp.ai.neural-nets
Subject: Re: : Step Function
Summary: is a function a set of ordered pairs?
Keywords: learning,generalization
Message-ID: <1697@cbnewsl.ATT.COM>
Date: 31 Aug 89 11:22:21 GMT
References: <1060@rex.cs.tulane.edu> <6980@sdcsvax.UCSD.Edu> <1989Aug30.162345.9569@elroy.jpl.nasa.gov>
Organization: AT&T Bell Laboratories
Lines: 31

> >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 [...]
> 
In article <1989Aug30.162345.9569@elroy.jpl.nasa.gov>, mathew@jane.Jpl.Nasa.Gov (Mathew Yeates) writes:

> 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".

Yes, I should stick to Valiant's paper. However, one thing: a known function
is, in most cases, more than a set of ordered pairs. It is a set of ordered
pairs related in some way. Discover the relation and no further examples
are needed to have complete knowledge of the entire set. The question of
"learnability" is whether the function, or rule, can possibly be
extracted from a set of samples *with probability of error less than some
value*. This is one mistake I made when I said "100% confidence"--that's
not possible.

However, getting back to X-OR, this probability of error = 0.5, clearly
too high to consider it learnable.

Aside: someone commented that learnability should be defined dependent
on architecture. I don't see why.

	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	~  	 Tony Russo		" Surrender to the void."	~
	~   apr@cbnewsl.ATT.COM		   put disclaimer here		~
	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~