The DOI matches its Crossref record; 41 of the 41 references it cites were found in a registry or an index.
The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network
Abstract
Sample complexity results from computational learning theory, when applied to neural network learning for pattern classification problems, suggest that for good generalization performance the number of training examples should grow at least linearly with the number of adjustable parameters in the network. Results in this paper show that if a large neural network is used for a pattern classification problem and the learning algorithm finds a network with small weights that has small squared error on the training patterns, then the generalization performance depends on the size of the weights rather than the number of weights. For example, consider a two-layer feedforward network of sigmoid units, in which the sum of the magnitudes of the weights associated with each unit is bounded by A and the input dimension is n. We show that the misclassification probability is no more than a certain error estimate (that is related to squared error on the training set) plus A/sup 3/ /spl radic/((log n)/m) (ignoring log A and log m factors), where m is the number of training patterns. This may explain the generalization performance of neural networks, particularly when the number of training examples is considerably smaller than the number of weights. It also supports heuristics (such as weight decay and early stopping) that attempt to keep the weights small during training. The proof techniques appear to be useful for the analysis of other pattern classifiers: when the input domain is a totally bounded metric space, we use the same approach to give upper bounds on misclassification probability for classifiers with decision boundaries that are far from the training examples.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A decision-theoretic generalization of on-line learning and an application to boosting
Freund, Y., & Schapire, R. E. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1504 · Cited by 20,466
A training algorithm for optimal margin classifiers
Boser, B. E., Guyon, I. M., & Vapnik, V. N. (1992) · Proceedings of the fifth annual workshop on Computational learning theory · doi:10.1145/130385.130401 · Cited by 11,992
Probability Inequalities for sums of Bounded Random Variables
Hoeffding, W. (1994) · Springer Series in Statistics · doi:10.1007/978-1-4612-0865-5_26 · Cited by 6,666
Introduction to the theory of neural computation
(1994) · Neural Networks · doi:10.1016/0893-6080(94)90014-0 · Cited by 6,401
Probability Inequalities for Sums of Bounded Random Variables
Hoeffding, W. (1963) · Journal of the American Statistical Association · doi:10.1080/01621459.1963.10500830 · Cited by 4,852
A Probabilistic Theory of Pattern Recognition
Devroye, L., Györfi, L., & Lugosi, G. (1996) · Stochastic Modelling and Applied Probability · doi:10.1007/978-1-4612-0711-5 · Cited by 3,274
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (2015) · Measures of Complexity · doi:10.1007/978-3-319-21852-6_3 · Cited by 3,105
Universal approximation bounds for superpositions of a sigmoidal function
Barron, A. R. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.256500 · Cited by 2,804
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (1971) · Theory of Probability & Its Applications · doi:10.1137/1116025 · Cited by 2,448
Boosting the margin: a new explanation for the effectiveness of voting methods
Bartlett, P., Freund, Y., Lee, W. S., & Schapire, R. E. (1998) · The Annals of Statistics · doi:10.1214/aos/1024691352 · Cited by 2,306
Self-citationEstimation of Dependences Based on Empirical Data
Vapnik, V. (2006) · Information Science and Statistics · doi:10.1007/0-387-34239-7 · Cited by 2,238
Convergence of Stochastic Processes.
Robinson, P. M., & Pollard, D. (1985) · Economica · doi:10.2307/2553898 · Cited by 2,184
Convergence of Stochastic Processes
Pollard, D. (1984) · Springer Series in Statistics · doi:10.1007/978-1-4612-5254-2 · Cited by 1,841
Learnability and the Vapnik-Chervonenkis dimension
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989) · Journal of the ACM · doi:10.1145/76359.76371 · Cited by 1,839
What Size Net Gives Valid Generalization?
Baum, E. B., & Haussler, D. (1989) · Neural Computation · doi:10.1162/neco.1989.1.1.151 · Cited by 1,541
(2017) · Approximation Techniques for Engineers · doi:10.1201/9781315205007-4 · Cited by 1,155
Decision theoretic generalizations of the PAC model for neural net and other learning applications
Haussler, D. (1992) · Information and Computation · doi:10.1016/0890-5401(92)90010-d · Cited by 843
Estimation of Dependences Based on Empirical Data.
Shoesmith, E., Vapnik, V., & Kotz, S. (1984) · The Statistician · doi:10.2307/2988246 · Cited by 764
Boosting the margin: A new explanation for the effectiveness of voting methods
Schapire, R. E., Freund, Y., Barlett, P., & Lee, W. S. (1997) · Cited by 711
Jones, L. K. (1992) · The Annals of Statistics · doi:10.1214/aos/1176348546 · Cited by 474
Learning to Tell Two Spirals Apart
Lang, K. J., & Witbrock, M. J. (1988) · doi:10.13140/2.1.3459.2329 · Cited by 421
A general lower bound on the number of examples needed for learning
Ehrenfeucht, A., Haussler, D., Kearns, M., & Valiant, L. (1989) · Information and Computation · doi:10.1016/0890-5401(89)90002-3 · Cited by 403
Efficient distribution-free learning of probabilistic concepts
Kearns, M. J., & Schapire, R. E. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80062-5 · Cited by 373
Scale-sensitive dimensions, uniform convergence, and learnability
Alon, N., Ben-David, S., Cesa-Bianchi, N., & Haussler, D. (1997) · Journal of the ACM · doi:10.1145/263867.263927 · Cited by 340
𝜀-entropy and 𝜀-capacity of sets in functional spaces
Kolmogorov, A. N. A. T. (1961) · Translations - American Mathematical Society/Translations · doi:10.1090/trans2/017/10 · Cited by 285
For Valid Generalization the Size of the Weights is More Important than the Size of the Network
Bartlett, P. L. (1996) · Cited by 213
Self-citationWhat Size Neural Network Gives Optimal Generalization? Convergence Properties of Backpropagation
Lawrence, S., Giles, C. L., & Tsoi, A. C. (1998) · University Libraries (University of Maryland) · Cited by 209
Automatic Capacity Tuning of Very Large VC-Dimension Classifiers
Guyon, I., Boser, B. E., & Vapnik, V. N. (1992) · Cited by 190
Feedforward nets for interpolation and classification
Sontag, E. D. (1992) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(92)90039-l · Cited by 158
Efficient agnostic learning of neural networks with bounded fan-in
Lee, W. S., Bartlett, P. L., & Williamson, R. C. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556601 · Cited by 150
Self-citationCharacterizations of Learnability for Classes of {0, ..., n)-Valued Functions
Ben-David, S., Cesa‐Bianchi, N., Haussler, D. H., & Long, P. M. (1995) · Journal of Computer and System Sciences · doi:10.1006/jcss.1995.1008 · Cited by 92
A generalization of Sauer's lemma
Haussler, D. H., & Long, P. M. (1995) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(95)90001-2 · Cited by 86
Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers
Goldberg, P. W., & Jerrum, M. (1995) · Machine Learning · doi:10.1007/bf00993408 · Cited by 80
A framework for structural risk minimisation
Shawe-Taylor, J. S., Bartlett, P. L., Williamson, R. C., & Anthony, M. (1996) · Conference on Learning Theory · doi:10.1145/238061.238070 · Cited by 79
Self-citationPolynomial bounds for VC dimension of sigmoidal neural networks
Karpiński, M., & Macintyre, A. J. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225118 · Cited by 75
Asymptotic distribution of the errors in scalar and vector quantizers
Lee, D. H., & Neuhoff, D. L. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.485715 · Cited by 58
Efficient distribution-free learning of probabilistic concepts
Kearns, M. J., & Schapire, R. E. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89557 · Cited by 58
Function Learning from Interpolation
Anthony, M., & Bartlett, P. L. (2000) · Combinatorics Probability Computing · doi:10.1017/s0963548300004247 · Cited by 54
Self-citationA result of Vapnik with applications
Anthony, M., & Shawe-Taylor, J. (1993) · Discrete Applied Mathematics · doi:10.1016/0166-218x(93)90126-9 · Cited by 48
Prediction, Learning, Uniform Convergence, and Scale-Sensitive Dimensions
Bartlett, P. L., & Long, P. M. (1998) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1557 · Cited by 48
Self-citation(1996)
Cited by
Extreme learning machine: Theory and applications
Huang, G.-B., Zhu, Q.-Y., & Siew, C.-K. (2006) · Neurocomputing · doi:10.1016/j.neucom.2005.12.126 · Cited by 13,285
Kernel Methods for Pattern Analysis
Shawe-Taylor, J., & Cristianini, N. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511809682 · Cited by 6,587
Extreme Learning Machine for Regression and Multiclass Classification
Huang, G.-B., Zhou, H., Ding, X., & Zhang, R. (2012) · IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) · doi:10.1109/tsmcb.2011.2168604 · Cited by 5,550
Extreme learning machine: a new learning scheme of feedforward neural networks
Huang, G.-B., Zhu, Q.-Y., & Siew, C.-K. (2005) · 2004 IEEE International Joint Conference on Neural Networks (IEEE Cat. No.04CH37541) · doi:10.1109/ijcnn.2004.1380068 · Cited by 4,084
Understanding deep learning requires rethinking generalization
Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2016) · arXiv · doi:10.48550/arxiv.1611.03530 · Cited by 2,838
Metadata
- Authors
- Bartlett, P. L.
- Venue
- IEEE Transactions on Information Theory
- Published
- 1998-03
- Volume
- 44
- Issue
- 2
- Pages
- 525-536
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2099579348
- Cited by
- 1,166
- References
- 41
- FWCI
- 36.32
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.