The Bin Model

Yaser Abu-Mostafa                    Xubo Song
Learning Systems Group               Dept. of Electrical Engineering
California Institute of Technology   Oregon Graduate Institute
Pasadena, CA, 91125                  Beaverton, OR, 97006

Alexander Nicholson                  Malik Magdon-Ismail
Learning Systems Group               Dept. of Computer Science
California Institute of Technology   Rensselaer Polytechnical Institute
Pasadena, CA, 91125                  Troy, NY, 12180


Abstract:

We propose a novel theoretical framework for understanding
learning and generalization which we call the bin model.  Using
the bin model, a closed form is derived for the generalization
error that estimates the out-of-sample performance in terms of
the in-sample performance.  We address the problem of
overfitting, and show that using a simple exhaustive learning
algorithm it does not arise.  This is independent of the target
function, input distribution and learning model, and remains
true even with noisy data sets.  We apply our analysis to both
classification and regression problems and give an example of
how it may be used efficiently in practice.