Path: utzoo!attcan!utgpu!watmath!att!cbnewsl!apr
From: apr@cbnewsl.ATT.COM (anthony.p.russo)
Newsgroups: comp.ai.neural-nets
Subject: Re: : Step Function
Summary: learnable with *bias*
Message-ID: <1683@cbnewsl.ATT.COM>
Date: 30 Aug 89 12:55:37 GMT
References: <1060@rex.cs.tulane.edu> <6980@sdcsvax.UCSD.Edu> <17522@bellcore.bellcore.com>
Organization: AT&T Bell Laboratories
Lines: 37

> In article<1667@cbnewsl.ATT.COM> I wrote:
> >X-OR is not learnable. If you are given the first three entries in the truth
> >table, you could not possibly generalize to the last entry with
> >any confidence. 
> 
In article <17522@bellcore.bellcore.com>, ackley@jeeves.bellcore.com (David H Ackley) writes:
> 
> This renders the term "learnable" meaningless.  Over the space of
> boolean functions, your claim is equally true of all of them.  Without
> some kind of preference structure or bias over the space, both outputs
> are equally likely for the last row, regardless of the rest of the
> table.  If you do allow such biases, I can pick one (say, a "parity
> bias") that makes XOR "learnable".
> 
I agree that X-OR is learnable *with* bias. That however, is not the
definition of "learnable" in the strictest sense. I won't attempt
to prove or disprove your claim regarding all boolean functions,
but why must boolean functions be learnable at all? When you saw
X-OR for the first time, you most likely *memorized* the truth table.
If not, then after *all four* entries, you determined the rule
that if both inputs are equal, output "0"; else output "1".
Could you have determined this rule with just three examples? No.
How would you have chosen a bias? 

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

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