Can neural networks do better than the Vapnik-Chervonenkis bounds?

Neural Information Processing SystemsPublished 1 October 1990

David Cohn, Gerald Tesauro

Citations22

TL;DR

A series of careful numerical experiments are described, which find that, in some cases, the average generalization is significantly better than the VC bound: the approach to perfect performance is exponential in the number of examples m, rather than the 1/m result of the bound.

Abstract

We describe a series of careful numerical experiments which measure the average generalization capability of neural networks trained on a variety of simple functions. These experiments are designed to test whether average generalization performance can surpass the worst-case bounds obtained from formal learning theory using the Vapnik-Chervonenkis dimension (Blumer et al., 1989). We indeed find that, in some cases, the average generalization is significantly better than the VC bound: the approach to perfect performance is exponential in the number of examples m, rather than the 1/m result of the bound. In other cases, we do find the 1/m behavior of the VC bound, and in these cases, the numerical prefactor is closely related to prefactor contained in the bound.

Keywords

Computer Science

Learning Internal Representations by Error Propagation

16,235 Citations1985David E. Rumelhart, Geoffrey E. Hinton +1 more

Journal of the ACMLearnability and the Vapnik-Chervonenkis dimension

1,852 Citations1989Anselm Blumer, Andrzej Ehrenfeucht +2 more

This paper shows that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned.

View PDF

Neural ComputationWhat Size Net Gives Valid Generalization?

1,555 Citations1989Eric B. Baum, David Haussler

It is shown that if m O(W/ ∊ log N/∊) random examples can be loaded on a feedforward network of linear threshold functions with N nodes and W weights, so that at least a fraction 1 ∊/2 of the examples are correctly classified, then one has confidence approaching certainty that the network will correctly classify a fraction 2 ∊ of future test examples drawn from the same distribution.

Consistent inference of probabilities in layered networks: predictions and generalizations

157 Citations1989Tishby, Левин +1 more

The problem of learning a general input-output relation using a layered neural network is discussed in a statistical framework and the authors arrive at a Gibbs distribution on a canonical ensemble of networks with the same architecture.

Neural ComputationExhaustive Learning

73 Citations1990Daniel Schwartz, Vijay K. Samalam +2 more

A simple Boolean learning problem involving networks with binary weights is numerically solved to obtain the entropy Sm and the average generalization ability Gm as a function of the size m of the training set.

Neural Information Processing SystemsScaling and Generalization in Neural Networks: A Case Study

53 Citations1988Subutai Ahmad, Gerald Tesauro

It is found that many aspects of generalization in multilayer networks learning large, difficult tasks are reproduced in this simple domain, in which concrete numerical results and even some analytic understanding can be achieved.