Models of generalization error in learning systems with training error selection

摘要

The paper presents general models of average generalization error in the case of selection of random binary valued classifiers with training error below a predefined threshold. The emphasis is on a model for very large learning systems. To that end we present rigorous calculations of thermodynamci limit and its essential dependence on "entropy distribution of error levels", although the proof is only outlined. The formal results are illustrated on examples of Ising perceptron and homogeneous perceptron compared against popular universal VC-bounds. Dramatic differences in scaled learning curves in these two examples allow us to conclude that at least some statistical properties of the learning system have to be taken into account it tight models of generalization at low training sample sizes are desired.