What Size Net Gives Valid Generalization?
Eric B. Baum, David H. Haussler · Neural Computation · 1989
We address the question of when a network can be expected to generalize from m random training examples chosen from some arbitrary probability distribution, assuming that future test examples are drawn from the same distribution. Among our results are the following bounds on appropriate sample vs. network size. Assume 0 < ∊ ≤ 1/8. We show 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 1 − ∊ of future test examples drawn from the same distribution. Conversely, for fully-connected feedforward nets with one hidden layer, any learning algorithm using fewer than Ω(W/∊) random training examples will, for some distributions of examples consistent with an appropriate weight choice, fail at least some fixed fraction of the time to find a weight choice that will correctly classify more than a 1 − ∊ fraction of the future test examples.
Cited by 1,541 works. doi:10.1162/neco.1989.1.1.151
Authors
References
- Pattern classification and scene analysis
- Backpropagation Applied to Handwritten Zip Code Recognition
- A Theory of the Learnable
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Estimation of Dependences Based on Empirical Data
- Large Automatic Learning, Rule Extraction, and Generalization.
- Parallel Networks that Learn to Pronounce English Text
- Learnability and the Vapnik-Chervonenkis dimension
- Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
- Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition