new paper

[dhw@santafe.edu]

                *** DO NOT FORWARD TO ANY OTHER LISTS ***




The following file has been placed in connectionists, under the name
wolpert.ex_learning.ps.Z.




	        AN INVESTIGATION OF EXHAUSTIVE LEARNING


				by

		David H. Wolpert, Alan Lapedes



Abstract: An extended version of the Bayesian formalism is reviewed.
We use this formalism to investigate the "exhaustive learning"
scenario, first introduced by Schwartz et al. This scenario is perhaps
the simplest possible supervised learning scenario. It is identical to
the noise-free "Gibbs learning" scenario studied recently by
Haussler et al., and can also be viewed as the zero-temperature limit
of the "statistical mechanics" work of Tishby et al. We prove that
the crucial "self-averaging" assumption invoked in the conventional
analysis of exhaustive learning does not hold in the simplest
non-trivial implementation of exhaustive learning. Therefore the
central result of that analysis, that generalization accuracy
necessarily rises as training set size is increased, is not generic.
More importantly, we show that if one (reasonably) changes the
definition of "generalization accuracy", to reflect only the error
on inputs outside of the training set, then this central result does
not hold even when the self-averaging assumption is valid, and even in
the limit of an infinite input space. This implies that the central
result is a reflection of the following simple phenomenon: if you add
an input/output pair to the training set, the number of distinct input
values on which you know exactly how you should guess has either
increased or stayed the same, and therefore your generalization
accuracy will either increase or stay the same. In addition to using
the extended Bayesian formalism to analyze the central result of the
conventional analysis of exhaustive learning, we also use it to
extend the results of exhaustive learning, to issues not considered in
previous analyses of the subject.





To retrieve this file:

unix> ftp cheops.cis.ohio-state.edu
Connected to cheops.cis.ohio-state.edu.
220 cheops.cis.ohio-state.edu FTP server ready.
Name: anonymous
331 Guest login ok, send ident as password.
Password:neuron
230 Guest login ok, access restrictions apply.
ftp> binary
200 Type set to I.
ftp> cd pub/neuroprose
250 CWD command successful.
ftp> get wolpert.ex_learning.ps.Z
200 PORT command successful.
150 Opening BINARY mode data connection for wolpert.ex_learning.ps.Z
226 Transfer complete.
100000 bytes sent in 3.14159 seconds
ftp> quit
221 Goodbye.
unix> uncompress wolpert.ex_learning.ps.Z
unix> lpr wolpert.ex_learning.ps (or however you print postscript)






Thanks to Jordan Pollack for maintaining this list.