Vapnik-Chervonenkis bounds for generalization

Abstract

We review the Vapnik and Chervonenkis theorem as applied to the problem of generalization. By combining some of the technical modifications proposed in the literature we derive tighter bounds and a new version of the theorem bounding the accuracy in the estimation of generalization probabilities from finite samples. A critical discussion and comparison with the results from statistical mechanics is given.