Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!bellcore!wind!ackley
From: ackley@wind.bellcore.com (David H Ackley)
Newsgroups: comp.ai.neural-nets
Subject: Re: : Step Function
Summary: abuse of terminology: learnable vs generalizable
Message-ID: <17521@bellcore.bellcore.com>
Date: 30 Aug 89 07:29:49 GMT
References: <1060@rex.cs.tulane.edu> <6980@sdcsvax.UCSD.Edu> <6981@sdcsvax.UCSD.Edu> <1667@cbnewsl.ATT.COM>
Sender: news@bellcore.bellcore.com
Reply-To: ackley@wind.UUCP (David H Ackley)
Organization: Bellcore, Morristown, NJ
Lines: 21

In article<1667@cbnewsl.ATT.COM> apr@cbnewsl.ATT.COM (anthony.p.russo) writes:
>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. 

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

Absolutely, generalization is a big important hard problem --- but
it's different than learnability, and it's not why XOR is famous.

| David Ackley   Cognitive Science Research Group |
|"To act or      Bell Communications Research Inc.|
|   to react,            ackley@flash.bellcore.com|
|     that is the question"    ...!bellcore!ackley|