pre-print announcement: Hoeffding Races - Accelerating Model Selection

[Oded Maron]

FTP-host: archive.cis.ohio-state.edu
FTP-file: pub/neuroprose/maron.hoeffding.ps.Z

The file maron.hoeffding.ps.Z is now available for
copying from the Neuroprose repository:

Hoeffding Races: Accelerating model selection for classification and
function approximation  (8 pages)

Oded Maron, MIT AI Lab and 
Andrew W. Moore, CMU


ABSTRACT: 

Selecting a good model of a set of input points by cross validation is a
computationally intensive process, especially if the number of
possible models or the number of training points is high.  Techniques
such as gradient descent are helpful in searching through the space of
models, but problems such as local minima, and more importantly, lack
of a distance metric between various models reduce the applicability
of these search methods. Hoeffding Races is a technique for finding a
good model for the data by quickly discarding bad models, and
concentrating the computational effort at differentiating between the
better ones.  This paper focuses on the special case of
leave-one-out cross validation applied to memory-based learning
algorithms, but we also argue that it is applicable to any class of
model selection problems.


This paper will appear in NIPS-6.

Maron, Oded and Moore, Andrew W. (1994). Hoeffding Races: Accelerating
model selection for classification and function approximation.  In
Cowan, J.D., Tesauro, G., and Alspector, J. (eds)., Advances in Neural
Information Processing Systems 6.  San Francisco, CA: Morgan Kaufmann
Publishers.