STATISTICAL-MECHANICS CALCULATION OF VAPNIK-CHERVONENKIS BOUNDS FOR PERCEPTRONS

Using the replica technique we calculate the maximal possible differen ce between the learning and the generalization error of a perceptron l earning a linearly separable Boolean classification from examples. We consider both spherical and Ising constraints on the couplings of the perceptron, investigate learnable as well as unlearnable problems and study the special situation where the class of perceptrons considered is restricted to the version space. The results are compared with the Vapnik-Chervorienkis bound and variants thereof. We find that these bo unds are asymptotically tight within logarithmic corrections.